引入
前一讲,我们介绍了什么是算法的量度,以及如何用渐进函数来看哪些对算法的复杂度影响最大,今天我们就来看看如何计算复杂度。
时间复杂度
定义:在进行算法分析时,语句总的执行次数 T(n) 是关于问题规模 n 的函数,进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。所以,算法的时间复杂度,就是算法的时间量度:
T(n)=O( f(n) )
时间复杂度:它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的
增长率相同
。称作算法的渐进时间复杂度,简称为时间复杂度。
f(n) 是问题规模 n 的某个函数(上节我们研究过,能够改变结果的那个函数)
- 记作:我们用大写 O()来体现算法的时间复杂度的记法,我们称之为大 O 记法。
一般来说,随着输入规模 n 的增大,T(n)增长最慢的算法为最优算法,也就是说 n 从 0 提升到10000000,但是算法的解题次数并没有随之提升,或者只有缓慢提升,表示算法非常的优秀。
计算时间复杂度
我们知道了什么是时间复杂度,那么我们该如何推到处这个大 O 阶呢?
- 加法常数:我们用
常数 1 取代
运行时间中的所有加法常数
。 - 最高价:在修改后的运行次数函数中,
只保留最高阶项
。 - 去乘数常数:如果最高项存在,且不是1,则
去除与这个最高项相乘的常数
。 - 最后:剩下的数就是大 O 阶
几个例子
我们用上面计算大 O 阶的方法,来解以下几个例题
常数阶
求下列算法的时间复杂度
1 | int sum=0,n=100; |
如果你数了数,有6行代码
f(n)=1+1+1+1+1+1
就说结果是 O(6)那就错了!
因为我们用
常数 1 取代运行时间中的所有加法常数`,所以,上面折麽多,我们将所有的都看做1,答案是O(1)。
sun=(1+n)*n/2;
这个也是一个普通项目,因为 cpu 只计算一次,所以这也是+1的常数项
线性阶
求下列算法的时间复杂度
1 | int i,n=100,sun=0; |
非嵌套循环一般都涉及线性阶,线性阶就是随着问题 n 的规模扩大,对应的计算次数呈直线增长。
在这个题里面,n=100,执行100次。所以,上面的例子时间复杂度 O(n)。
平方阶
求下列算法的时间复杂度
1 | int i,j,n=100,sun=0; |
这就是一个嵌套循环,也就是一个循环中包含另一个循环,那么实际执行下来,应该为100X100,也就是 $n^2$ ,所以这段代码的时间复杂度是$O(n^2)$。
如果,有三个嵌套循环呢?答案就是$O(n^3)$了!
所以,我们很容易得出,
循环的时间复杂度 == 循环体本身的复杂度 X 该循环题执行的次数
如果嵌套循环的循环次数不一致呢?
1 | int i,j,n=100; |
我们看到
- 外层循环0次,内层循环执行 n次
- 外层循环1次,内层循环执行 n-1次
- 外层循环2次,内层循环执行 n-2次
以此类推
其实这就是 n(n+1)/2 就是我们一开始那个求和公式。
$n(n+1)/2=n^2/2+n/2$
第一条,没有常数相加,不执行操作。
第二条,只保留最高项,所以 n/2 要去掉
第三条,1/2 乘以 $n^2$ ,n 的指数不为1,所以 1/2 要去掉
结果,$O(n^2)$
对数阶
求下列算法的时间复杂度
1 | int i=1,n=100; |
我们分析一下循环如何跳出,即
i=i*2 也就是 x 个 2相乘
$2^x=n$ 也就是 $x=log_{2}^{n}$
所以,时间复杂度位 O(Logn);
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。