先给结论：
- 结论1： 时间复杂度是 O(1) 最牛逼， 是 O(n^2) 以及比它效率更优的可以被接受，时间复杂度比 O(n^2) 效率还差的的最好不用。优劣排行情况：
O(1) < O(lgn) < O(n) < O(nlgn) < O(n^2) < O(n^3) < O(2^n) < O(n!)- 结论2： 典型排序算法的优劣和它们的平均表现 ( 更多相关信息可见 http://bigocheatsheet.com/ )
图0. 常见排序算法时间复杂度总结
算法的基本操作和它的复杂程度：
一段代码，最直白的办法是用分号“；”来划分程序语句的基本操作（不同语言有所区别），然后对每个基本操作分析它运行时的重复次数，称为“频度”。
举个例子：
// (基本操作1，频度为1)
var sum = 0;
// (基本操作2，i=0的频度为1)
// (基本操作3，i<n; i++; 的频度为 n)
for(var i=0; i<n; i++) {
// (基本操作4，j=0的频度为1)
// (基本操作5，j<n; j++; 的频度为 n^2)
for(var j=0; j<n; j++) {
// ( 基本操作6，sum++ 的频度为 n^2)
sum++;
}
} ;
这里定义 语句频度 的函数 T(n)，是一个关于程序输入规模n的函数，即 T(n)的函数图可以表示随着 n 的值增加， 语句频度 （复杂程度，或者说语句重复次数）的走势。上面例子的 T(n) = 1+1+1+ n + n^2 + n^2 = 3 + n + 2n^2
图1. 输入规模-语句频度 示意图
大O表示法详说：
这里定义当 n 趋近于无穷大 ∞ 时，如果 lim(T(n) / f(n))的值为不等于0的常数，则称 f(n) 是 T(n) 的同数量级函数。记作 T(n) = O(f(n)) 。
通常的做法是，将 T(n) 函数表达式做以下处理，忽略常量、低次幂、最高次幂的常数系数，就可以令 f(n) 等于 T(n) 的数量级。举个例子：对于 T(n) = 2n^2 + n + 1 ，则有 O(f(n)) = O(n^2) 。
在这个例子中， f(n) 是个辅助函数，没有特别具体的规定，但一般都是取尽可能简单的函数，如 O(f(n)) = O(2n^2 + n + 1) = O(3n^2 + n + 3) = O(7n^2 + n) = O ( n^2 )，一般都只用 O(n^2)表示就可以了，这时候
f(n) = n^2，可以扣回定义试试看极限是否是不为零的常数
(注： n-> ∞ , lim[2 + n^(-1) + n^(-2)] = 2)。
基于前文 图1 中语句频度随输入规模n而变化的情况，用大O表示法可以直观地如 图2 所示：
图2. 大O复杂度示意图
举些例子：
时间复杂度为 O(n) 的例子：
// (基本操作1，频度为1)
var sum=0;
// (基本操作2，i=1的频度为1 )
// (基本操作3，i<n; i++; 的频度为n )
for(var i=0; i<n; i++) {
// ( 基本操作4，sum++的频度为n)
sum++；
} ;
// (基本操作1，频度为1)
var i = 0;
// (基本操作2，i<n的频度为n)
while(i < n) {
// ( 基本操作3，i++的频度为n)
i++;
} ;
时间复杂度为 O(lgn) 的例子：
// (基本操作1，频度为1)
var sum=0;
// (基本操作2，i=0的频度为1；)
// (基本操作3，i<n; i = i*2; 的频度为log2n，即以2为底n的对数 )
for(var i=0; i<n; i = i*2;) {
// ( 基本操作4，sum++的频度为log2n)
sum++；
} ;
注：基本操作3的频度设为t，当2^t < n 时，for 循环结束，对式子中小于号左右两端取以2为底数的对数，得到 t < log2n，所以在最坏的情况下，基本操作3会重复执行log2n次。则 T(n) = 1 + 1 + log2n + log2n = 2+2log2n, O(n) = log2n。又因为对数换底公式，loga n和 logb n只有一个常数因子不同，这个常数因子在大O记法中被丢弃，所以 O(n) = log2 n = lgn
时间复杂度为 O(nlgn) 的例子：
// (基本操作1，频度为1)
var num1, num2;
// (基本操作2，i=0频度为1)
// (基本操作3，i<n; i++频度为 n)
for(var i=0; i<n; i++){
// (基本操作4，频度为 n)
num1 += 1;
// (基本操作5，j=1频度为 n)
// (基本操作6，j<=n; j*=2频度为 n*log2n)
for(var j=1; j<=n; j*=2){
num2 += num1; // (基本操作7，频度为 n*log2n)
}
}
则 T(n) = 1 + 1 + n + n + nlog2n + nlog2n = 2(1 + n + nlog2n), O(n) = n log2n
时间复杂度为 O(n^2) 的例子： 本文第一个代码块就是。
小结：大O表示法很简单，时间复杂度也不难理解，本人在整个认知过程中在对数复杂度绕不过来弯，其实理解了什么是“频度”以及计算复杂度的初衷就能想明白。最后，给数学不好的我：
for(var j=1; j<n; j *= 2) {
// inside for-loop
}
对数复杂度怎么算出来的
LaTeX很优雅，值得学习。
参考：
http://blog.csdn.net/zolalad/article/details/11848739
http://univasity.iteye.com/blog/1164707
http://bigocheatsheet.com/
网友评论