大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 = log₂n

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)。

空间复杂度（略）