算法表示概念扫盲 | 您所在的位置:网站首页 › lg35等于多少 › 算法表示概念扫盲 |
1.常数阶O(1) 常数又称定数,是指一个数值不变的常量,与之相反的是变量 为什么下面算法的时间复杂度不是O(3),而是O(1)。 int sum = 0,n = 100; /*执行一次*/ sum = (1+n)*n/2; /*执行一次*/ printf("%d", sum); /*行次*/这个算法的运行次数函数是f(n)=3。根据我们推导大O阶的方法,第一步就是把常数项3改为1。在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的时间复杂度为O(1)。 另外,我们试想一下,如果这个算法当中的语句sum=(1+n)*n/2有10句,即: int sum = 0, n = 100; /*执行1次*/ sum = (1+n)*n/2; /*执行第1次*/ sum = (1+n)*n/2; /*执行第2次*/ sum = (1+n)*n/2; /*执行第3次*/ sum = (1+n)*n/2; /*执行第4次*/ sum = (1+n)*n/2; /*执行第5次*/ sum = (1+n)*n/2; /*执行第6次*/ sum = (1+n)*n/2; /*执行第7次*/ sum = (1+n)*n/2; /*执行第8次*/ sum = (1+n)*n/2; /*执行第9次*/ sum = (1+n)*n/2; /*执行第10次*/ printf("%d",sum); /*执行1次*/事实上无论n为多少,上面的两段代码就是3次和12次执行的差异。这种与问题的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的时间复杂度,又叫常数阶。 注意:不管这个常数是多少,我们都记作O(1),而不能是O(3)、O(12)等其他任何数字,这是初学者常常犯的错误。
推导大O阶方法 1.用常数1取代运行时间中的所有加法常数 2.在修改后的运行次数函数中,只保留最高阶项 3.如果最高阶项存在且不是1,则去除与这个项相乘的常数 2.对数阶O(log2n) 对数 如果a的x次方等于N(a>0,且a不等于1),那么数x叫做以a为底N的对数(logarithm),记作x=logaN, 。其中,a叫做对数的底数,N叫做真数。 5^2 = 25 , 记作 2= log5 25 对数是一种运算,与指数是互逆的运算。例如 ① 3^2=9 2=log9; ② 4^(3/2)=8 3/2=log8; ③ 10^n=35 n=lg35。为了使用方便,人们逐渐把以10为底的常用对数记作lgN
对数阶 int count = 1; while (count < n) { count = count * 2; /* 时间复杂度为O(1)的程序步骤序列 */ }由于每次count乘以2之后,就距离n更近了一分。 也就是说,有多少个2相乘后大于n,则会退出循环。 由2^x=n得到x=log2n。所以这个循环的时间复杂度为O(logn)。 3.线性阶O(n) 执行时间随问题规模增长呈正比例增长 data = [ 8,3,67,77,78,22,6,3,88,21,2] find_num = 22 for i in data: if i == 22: print("find",find_num,i )4.线性对数阶O(nlog2n) 原文就为空 5.平方阶O(n^2)for i in range(100): for k in range(100): print(i,k) 立方阶O(n^3) k次方阶O(n^k), 指数阶O(2^n)。 随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
作者:小家电维修 转世燕还故榻,为你衔来二月的花。
|
CopyRight 2018-2019 实验室设备网 版权所有 |