大O符号表示法
又称算法的渐进时间/空间复杂度，它不是用于反应算法真实的执行时间/空间的，而是用来表示代码执行时间/空间的增长变化趋势。
常见的时间复杂度量级
- 常数阶O(1)
- 对数阶O(logN)
- 线性阶O(n)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K次方阶O(n^k)
- 指数阶(2^n)
O(n) 模型
for(int i=0;i<n;i++){
//todo
}
O(logN) 模型
for(int i=0;i<n;i*=2){
//todo
}
假设x为循环次数，有2^x=n，即x = log2n
O(nlogN)模型
将O(logN) 模型循环n遍
for(int i=0; i<n; i++){
for(int j=0; j<n; j*=2){
//todo
}
}
O(n²)模型
将O(n) 模型循环n遍
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
//todo
}
}
O(2^n)模型
long aFunc(int n) {
if (n <= 1) {
return 1;
} else {
return aFunc(n - 1) + aFunc(n - 2);
}
}
显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列，通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。 所以该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。
