算法就是为了提高代码运行效率,衡量算法的性能有两个考量指标:
时间复杂度与空间复杂度,它会伴随你学习算法的始终。
今天先谈一谈时间复杂度,在学习时间复杂度之前,我建议你先思考为什么需要复杂度。
插一句,很多时候,了解一个知识为什么出现可能比知识本身还要重要,无论是算法学习还是整个计算机领域。
为什么需要分析复杂度
时间复杂度,不就是衡量代码的执行时长吗,我直接写好代码在机子上一跑不就知道了吗。
为什么要多此一举?只是为了更学术、更官方吗?
-
测试环境
同样的代码在不同的机器上执行速度不同,每台机器的配置高低会影响代码执行效率。甚至,在你的电脑上,A算法比B算法快,到了我的电脑上反而B算法更快。
-
数据规模
拿排序来说,对十个数据排序和对十万个数据排序当然执行时间不一样,数据规模太小则无法反应算法的性能。举个栗子,快速排序是优于选择排序的,但数据规模较小时,快排却没选排快。
那怎么办,难道每次介绍算法前都要写上:在XXX配置和XXX数据规模下,算法执行效率XXX。
那太麻烦了,为此引入一个不需要考虑以上差异的衡量算法性能的标准,就是今天所说的时间复杂度分析。
大 O 表示法
知道了时间复杂度的由来,再谈谈该怎么表示。算法的执行效率就是看算法的执行时间,那怎么在不执行代码的情况下知道执行时间呢?
最朴素的办法就是看代码执行了多少行呗,举个栗子,看一段简单代码:
int func(int n) {
int sum = 0;
for(int i = 1; i <= n; ++i) {
sum = 0;
for(int j = 1; j <= n; ++j) {
sum = i + j;
}
}
return sum;
}
作为粗略估计,假设每行代码的执行时间一样,记为TIME。现在来计算这段代码执行时间是多少,第2行执行一次只需要一个TIME,第3、4行外层循环执行了n次,所以需要2n个TIME,而第5、6行内层循环执行了n2次,所以需要2n2个TIME。
所以,这段代码的执行时间T(n) = (2n^2 + 2n + 1) * TIME。
TIME可以认为是一个常量,代表一行代码的平均执行时间。然后可以发现,执行时间与代码执行次数n成正比。
为了方便表示,我们把代码执行次数记为f(n),那么上面那个例子的代码执行次数f(n) = 2n^2 + 2n + 1。
所以T(n) = f(n) * TIME,可以看出代码执行时间与代码执行次数成正比,可以进一步表示为:T(n) = O( f(n) ),O表示T(n)与f(n)成正比。
上面那个例子用大O表示法就是T(n) = O(2n^2 + 2n + 1),请注意,大O表示法其实不指代码的具体运行时间,而是表示代码执行时间随数据规模增长的变化趋势。
当数据规模很大时,也就是n很大时,公式中的常量、系数和低阶都可以忽略,因为此时这三部分对n的增长趋势影响。
最终,上面那个例子的大O复杂度表示法就是 T(n) = O( n^2 )。
常见时间复杂度
常见原则:
-
加法原则:
例如顺序执行三个循环,第一个循环执行100次,第二个循环执行n次,第三个循环执行n2次,T(n) = O(100 + n + n2),忽略常量和低阶就是T(n) = O( n^2 )。
-
乘法原则:
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。例如两层嵌套循环,外层n次,内存n次,则T(n) = O(n * n)。
常见复杂度案例:
- 常量阶:O( 1 ),并不是代表只执行了1行代码,只要算法里没有循环和递归,哪怕顺序执行了一万行代码,也算O( 1 )。
- 对数阶:O( logn )、O( nlogn ),常见于递归树的分析,也是比较难分析的一类复杂度。
- 线性阶:O( n ),常见于循环遍历。
- k方阶:O( n2 )、O( n3 )、...O( n^k ),常见于嵌套循环。
以上罗列的复杂度量级可以称为多项式量级,另外还有两个非多项式量级:
指数阶O( 2^n ) 和 阶乘阶O( n! ),非多项式复杂度是很低效的算法,不再展开细说。
END
为了不考虑机器配置和数据规模的差异所带来的影响,引入了时间复杂度这个概念。
而时间复杂度就是描述算法执行时间随数据规模增长所表现的趋势。
在学习算法的过程中,试着分析所学算法的时间复杂度,慢慢的会对时间复杂度有更深入的理解。
评论区