前言
衡量一个算法的效率，可以从时间复杂度T(n) 和 空间复杂度S(n) 去分析。时间复杂度衡量算法执行的时间，空间复杂度衡量算法执行消耗的内存大小，默认情况下都是分析最坏情况下的复杂度。首先引入一个辅助函数f(n)，可理解为算法中代码的执行次数(也称为频度)，如下面代码：
代价 次数
for(int i = 0; i < n; i++){ c1 n
int j = i; c2 n-1
cout << j << endl; c3 n-1
}
此时f(n)=c1n + c2(n-1) + c3(n-1)。
时间复杂度
1.概念
对于时间复杂度来说，代价即为当前行代码执行时间，当n趋于无穷大的时候，记T(n)=O(f(n))，被称为算法的渐进时间复杂度，又简称为时间复杂度，大O给出的是函数f(n)唯一的的渐进上界。因为n趋于无穷大，所以f(n)的常数项变化对整体影响不大，直接去掉。所以对于上述代码，T(n)=O(n)。
2.常见时间复杂度
- 常数阶
T(n)=O(1)
int i = 0;
- 线性阶
T(n) = O(n)
for(int i = 0; i < n; i++);
- 平方阶
T(n)=O(n2)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
- 对数阶
T(n)=O(logn)
int i = 2;
while(i < n) i *= 2;
这里说一下，设循环次数为t，2^t < n ==> t < logn。
3.求解含递归算法的时间复杂度
包含递归的算法很常见，比如熟悉的斐波那契数列：
int func(int n) {
if (n <= 1) return 1;
else return func(n - 1) + func(n - 2);
}
对于这种算法，上面介绍的常用时间复杂度有些力不从心。所以针对这种算法，我们直接将复杂度表示为T(n)=T(n-1)+T(n-2)+1，+1是指else中问题分解与解合并的代价。那问题是怎么去计算它出T(n)呢？这里介绍两种方法代入法和主方法。
代入法：首先猜测解的形式，然后通过归纳法求出解中的常数，并证明解是正确的。
对于斐波那契数列算法，我们猜测其解为T(n)=O(n^2)，那代入法要求证明，存在常数c>0，有T(n)<=cn^2，先假设此上界对于所有m<n都成立，然后代入递归式：
T(n) <= c(n-1)^2+c(n-2)^2+1
<= 2cn^2-6cn
<= cn^2。
其中对于c>=1，最后一步都成立。接着数学归纳法要求证明解在边界条件下也成立，如果成立，则猜想正确。
当n=1时，T(1)=1<=c;
因此，对于所有c>=1，都有T(n)<=cn^2，猜想成立。代入法的成功很大程度上看你猜测的解是否正确，很靠经验，偶尔还需要创造力。虽然如此，但在实际的分析中，它也是一个不错的方法。
主方法：主方法为形如T(n)=aT(n/b)+f(n)的递归式提供了一种"菜谱式"的求解方法。其中a>=1,b>1且为常数，f(n)是一个渐进正函数（即n趋近无穷时，f(n)是一个正数），n为非负整数。该递归式的含义是，将规模为n的问题分解成了a个子问题，每个子问题规模为n/b，而f(n)表示问题分解和和子问题解合并的代价。 主方法通过下面定理得到T(n)：
（1）若存在某个常数k>0，有
f(n)=O(n^logb(a-k))，则T(n)=Θ(n^logb(a))。
（2）若f(n)=Θ(n^logb(a))，则T(n)=Θ(n^logb(a)*lgn)。
（3）若存在某个常数k>0，有f(n)=Ω(n^logb(a+k))，且存在常数c<1和所有足够大的n有af(n/b)<=cf(n)，则T(n)=Θ(f(n))。
O表示小于等于（即上界），Θ表示等于，Ω表示大于等于（即下界），因此对上述定理归纳后可得：
（1）若
f(n)<=n^logb(a)，则T(n)=Θ(n^logb(a))。
（2）若f(n)==n^logb(a))，则T(n)=Θ(n^logb(a)*lgn)。
（3）若f(n)>=n^logb(a)，且存在常数c<1和所有足够大的n有af(n/b)<=cf(n)，则T(n)=Θ(f(n))。
主方法使用：
情况1：
T(n) = 9T(n/3) + n
a=9，b=3，nlogb(a)=n2，因为f(n)=n <= n^2，所以用定理1，得T(n)=Θ(n^2)。
情况2：
T(n) = T(2n/3) + 1
a=1，b=3/2，n^logb(a)=1，因为f(n)=1 == 1，所以用定理2，得T(n)=Θ(lgn)。
情况3：
T(n) = 3T(n/4) + nlgn
a=3，b=4，nlogb(a)=nlog4(3)<=n^0.793，因为f(n)=nlgn >= n^0.793，再当n足够大时，对于c=3/4，有af(n/b)<=cf(n)，所以用定理3，得T(n)=Θ(nlgn)。
4.常用时间复杂度比较
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
5.小结
观察算法中有几重for循环，只有一重则时间复杂度为n，二重则为n^2，依此类推，如果有二分则为logn，如果一个for循环套一个二分，那么时间复杂度则为nlogn，如果算法含有递归，则根据上面两种方法进行推导。
结尾
1.平均情况时间复杂度：
（1）上面讨论的都是最坏情况下得时间复杂度，而一般最好、最坏时间复杂度是在极端条件下出现的，发生的概率不大，不能代表平均水平。所以为了更好的表示算法复杂度，就引入平均时间复杂度。
（2）平均情况时间复杂度通过代码在所有可能情况下执行次数的加权平均值表示。虽然平均情况时间复杂度可以很好的反应算法的效率，但在实际应用中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。所以一般在没有特殊说明的情况下，时间复杂度都是指最坏时间复杂度。
2.空间复杂度：
空间复杂度S(n)表示一个算法在运行过程中临时占用存储空间得大小，它包括，为参数表中形参变量分配的存储空间和为函数体中定义的局部变量分配的存储空间两个部分。
3.最后说一句：
实际应用中，时间复杂度和空间复杂度需要合理的配合，如常用的通过牺牲空间复杂度来减小时间复杂度。
【关注公众号DoCode，每日一道LeetCode，将零碎时间利用起来】
