算法复杂度分析(1)

飞熊 • 2023年8月3日下午7:18 • 技术随笔 • 阅读 190

数学基础

如果存在常数c和n₀使得当N>=n₀时T(N)<=cf(N)，则记为T(N)=O(f(N))。

例如：虽然对于较小的N值1000N要比N²大，但N²以更快地速度增长，因此N²最终将是更大的函数。在这种情况下，N=1000是转折点。
如上面定义所说，最后总会存在某个点n₀从它以后cf(N)总是至少与T(N)一样大，从而若忽略常数因子，则f(N)至少与T(N)一样大。
在例子中，T(N)=1000N，f(N)=N²，n₀=1000而c=1。我们也可以让n₀=10而c=100。
因此可以说，1000N=O(N²)。这种记法称为大O标记法。

大O复杂度表示法

通过分析代码，总结了一个规律，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
把这个规律总结成一个公式。

T(n)=O(f(n))

其中，T(n) 它表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
当 n 很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了。

时间复杂度分析

只关注循环执行次数最多的一段代码
加法法则：总复杂度等于量级最大的那段代码的复杂度
T1(n)=O(f(n))，T2(n)=O(g(n))
则T(n)=T1(n)+T2(n)= O(f(n) + g(n)) = max(O(f(n)), O(g(n)))
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
T1(n)=O(f(n))，T2(n)=O(g(n))
则T(n)=T1(n)*T2(n)=O(f(n)*g(n))

常见时间复杂度实例

多项式量级

常量阶O(1)
注意它只是时间复杂度的一种表示方法，并不是只执行了一行代码。
对数阶O(logn)
可以把所有对数阶都记为O(logn) （忽略底数）。因为对数之间是可以相互转换的，例如log₃n = log₃2 * log₂n，其中log₃2是一个常数，采用大O标记复杂度的时候，可以忽略系数
线性对数阶O(nlogn)
可以参照前面的乘法法则，复杂度为O(logn)的代码循环执行n遍，就可以得到这个时间复杂度
线性阶O(n)
平方阶O(n²)
立方阶O(n³)
k次方阶O(n^k)