快
和
省
的问题,即如何让代码运行的更快,如何让代码更节省存储空间。一个非常重要的考量指标是算法的执行效率,分析方法有事后分析和提前预测两种–
事后统计法
和
时间、空间复杂度分析法
。
即让代码在计算机硬件上实际运行一遍,并监控和统计出算法执行实际花费的时间和占用的内存。这种方法很正确,但是有如下缺点:
因此我们需要一种方法,以便在构思和编写算法时,不用实际运行就可以粗略估算和预测算法的执行效率,这可以指导我们编写出符合业务要求且效率高的算法程序。
作为粗略估计,我们可以认为每行代码执行(读-运算-写)所需要的时间都一样,且假定为单位时间 unit_time。这里有两种情况:目标代码不包含循环;目标代码包含循环。对于前者,很简单,执行完一次就完了,执行时间是个固定值,这没什么好研究的;对于后者,由于非循环部分代码的执行时间是固定的,那么目标代码总体执行时间取决于循环体代码的执行时间,这由循环体行数以及各行循环的次数(可能出现嵌套循环),方便起见总计为循环 n 次,那么总的执行时间就是 n 的函数了,记为 T(n)。很显然,目标代码的执行时间 T(n) 与数据规模 n 成正比
,记为:
其中:T(n) 表示代码执行的时间,n 表示数据规模的大小(循环总次数),f(n)表示每行代码执行的次数总和,O表示正比关系。这就是大 O 时间复杂度表示法
。
注意,大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势
,所以也叫渐近时间复杂度,简称时间复杂度。
当 n 很大时,公式 f(n) 中的低阶、常量、系数并不左右增长趋势,可忽略
,而只需要关注最大量级的那部分即可。
如果 T1(n)=O(f(n)),T2(n)=O(g(n));那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))=O(max(f(n), g(n))).
如果 T1(n)=O(f(n)),T2(n)=O(g(n));那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).
注意
:复杂度分析无需记忆上述公式,只需多看案例多练习分析,就能掌握。
以上可组略分为两类:多项式量级和非多项式量级。只有 O(2n) 和 O(n!) 属于后者。
非多项式量级的时间复杂度算法,随着数据量的增大,算法执行的时间急剧增加,所以这些算法是非常低效的。
表示算法执行时间为常量的算法。一般情况下,只要算法中不存在循环、递归等操作,该算法的时间复杂度就是常量级。
可通过下面案例理解O(logn):循环体中 i = i * 2; 的执行次数为 log2n次
i=1;
while (i <= n) {
i = i * 2;
}
通过对数的换底公式
,其他任意底的对数都可以转换成常系数形式的log2n(Clog2n),而常系数又是可以忽略的,所以任意对数复杂度的算法可统一将其复杂度表示为logn
。
关于O(nlogn),通过时间复杂度乘法法则可知,O(nlogn) = O(n) * O(logn),可简单理解为复杂度为 O(logn) 的代码被循环执行了 n 遍。常见的归并排序、快速排序的时间复杂度就是 O(nlogn)。
两个数据规模未知
的算法的复杂度有如上表示。
复杂度分析并不难,关键在多练习!
运用概率知识算出的期望值(加权平均值)。
说明
:很多时候使用一个复杂度就可以满足需求,只有同一块代码块在不同情况下,时间复杂度有量级的差距时,才会使用最好、最坏和平均来区分。
一种特殊的平均情况时间复杂度