大O表示法：算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。
大小关系：
当n→∞时，\(ln^αn<<n^β<<a^n<<n!<<n^n\)（其中α>0，β>0，a>1）O(X)可以当成一个数进行运算，当所有式子运算结束后，查看数量级即可。
如 \(n^2*O(1)=O(n^2)\)，\(4O(2^{k-1})=2^{k+1}\)等比求和公式
\[Sn={{a_1(1-q^n)} \over {1-q}}={{a_1-a_nq} \over {1-q}}\]
迭代程序
方程法
- 题目：
int i=1;
while(i<=n) {
i=i*2;
}- 思路：
假设循环执行了k次，那么\(2^k\)≤n，则k≤logn，所以时间复杂度为T(n)=O(logn)
求和法
- 题目：
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
for(k=1; k<=j; k++)
x++;思路：
\({∑_{i=1}^{n}∑_{j=1}^{i}∑_{k=1}^{j}1}=∑∑j=∑i(i+1)/2=O(n^3)\)一次方（求和∑）→二次方
二次方（求和∑）→三次方
递归程序
主方法
- 分治法主定理：T[n] = aT[n/b] + f(n)，其中n为问题规模，a≥1 and b>1 是常量，并且f(n)是一个渐进正函数，也就是递归以外的计算时间，为了使用这个主定理，需要考虑下列三种情况：
- 如果f(n)=O(\(n^{log_ba-ε}\))（即 f(n)的指数小于\({log_ba}\)），对于某个常量ε>0成立（即 f(n)为\(n^{log_ba}\)的低阶无穷大），那么T(n)=O(\(n^{log_ba}\))（即 时间复杂度取决于高阶无穷大
） 如果f(n)=O(\(n^{log_ba}\))（即 f(n)的指数等于\({log_ba}\)）（即 f(n)为\(n^{log_ba}\)的同阶无穷大），那么T(n)=O(\(n^{log_ba}logn\))
如果f(n)=O(\(n^{log_ba+ε}\))（即 f(n)的指数大于\({log_ba}\)），对于某个常量ε>0成立，并且af(n/b)≤cf(n)，对于某个常量c<1(n足够大)成立（即 f(n)为\(n^{log_ba}\)的高阶无穷大），那么T(n)=O(f(n))
- 如果f(n)=O(\(n^{log_ba-ε}\))（即 f(n)的指数小于\({log_ba}\)），对于某个常量ε>0成立（即 f(n)为\(n^{log_ba}\)的低阶无穷大），那么T(n)=O(\(n^{log_ba}\))（即 时间复杂度取决于高阶无穷大
-
基本步骤：
- a=?,b=?,f(n)=?，满足主定理条件
- f(n)的指数>(=)(<)\(log_ba\)，若大于，则判断cf(n)≥a(n/b),(c<1)
- 故时间复杂度为O(?)
- 题目：
T(n)=3T(n/2)+\(n^2\) - 思路：
- 试试能不能使用主方法，a=3,b=2,f(n)=n^2满足条件
- 看看满足哪一种情况，由于\(log_23\)<2，且\(3n^2/4 < cn^2\)(c<1)，满足第三种情况，所以T(n)=O(n^2)
迭代法
-
基本步骤：题目T(n) = aT(n/b) + f(n)
- 根据题目，设n=\(b^k\)（这样可以消除n/b对我们判断的影响），S(k) = T(\(b^k\))（将原式子T(n)=T(\(b^k\))记为S(k)），则k=\(log_bn\)，并将从S(k)到S(1)依次列出来，如：
令 n=\(5^k\),S(k) = T(\(5^k\)),则k=\(log_5n\)，那么
\(S(k) = 6S(k-1) + 5^k\)，\((j=0)\)
\(S(k-1) = 6S(k-2) + 5^{k-1}\)，\((j=1)\)
...
\(S(1) = 6S(0) + 5\)，\((j=k-1)\) -
将左端为S(k-j)的式子乘上\(a^j\)之后全部加起来，即
\(S(k)*a^0+S(k-1)*a^1+S(k-2)*a^2+...+S(1)*a^{k-1}\)
就消去了所有中间项，得到S(k)=...，如：
\(S(k) = 6^k S(0) + [5^k + 6*5^{k-1} + ... + 6^{k-1}*5]\)
\(= 6^k*Θ(1) + 5*Θ(6^k) = Θ(6^k)\) -
写成T(n)的形式，即S(k)=T(\(b^k\))=T(n)=...（其中k=\(log_bn\)），如：
\(k=log_5n\)
\(T(n) = Θ(n^{ln6/ln5})\)
- 根据题目，设n=\(b^k\)（这样可以消除n/b对我们判断的影响），S(k) = T(\(b^k\))（将原式子T(n)=T(\(b^k\))记为S(k)），则k=\(log_bn\)，并将从S(k)到S(1)依次列出来，如：
- 题目：
//汉诺塔问题，假定move()的时间复杂度为O(1)
void hanoi(int n,char x,char y,char z) {
if(n == 1) {
move(x,1,z);
}else {
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,z);
}
}- 思路：
综合例题
一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度级别。
\[T(n)= \begin{cases} 1& \text{n=1}\\ 2T(n/2)+n& \text{n>1} \end{cases}\]
式中，n是问题的规模，为简单起见，设n是2的整数次幂。
- 主定理：
a=2,f(n)=n满足条件；
1=\(log_22\)，故时间复杂度为\(O(nlog_2n)\)
-
迭代法：
设n=\(2^k\)(k≥0)，则
\(T(2^k)=2T(2^{k-1})+2^k\)
\(T(2^{k-1})=2T(2^{k-2})+2^{k-1}\)
故，\(T(2^k)=2(2T(2^{k-2})+2^{k-1})+2^k=2^2T(2^{k-2})+2*2^k\)
由归纳法，得\(T(2^k)=2^iT(2^{k-i})+i*2^k\)
进而i取k时，得
\(T(2^k)=2^kT(2^{0})+k*2^k\)
即 \(T(n)=2^{log_2n}+log_2n*n=n(log_2n+1)\)
也就是\(O(nlog_2n)\)主定理起验证作用，一般用迭代法确保满分。
求 T(n)=2T(n/4)+n^2的非递归解并证明。
- 主定理：
a=2,b=4,f(n)=n^2满足主定理条件；
2>log_42,cf(n)≥2(n/4)^2=n^2/8,(c<1)成立；
故时间复杂度为\(O(n^2)\)
-
迭代法：
设\(n=4^k\)(k≥0)，则
\(T(4^k)=2T(4^{k-1})+4^{2k}\)
\(T(4^{k-1})=2T(4^{k-2})+4^{2(k-1)}\)
故，\(T(4^k)=2(2T(4^{k-2})+4^{2(k-1)})+4^{2k}=2^2T(4^{k-2})+2*4^{2(k-1)}+4^{2k}\)
\(T(4^k)=2^iT(4^{k-i})+2^{i-1}*4^{2(k-i)}+...+4^{2k}\)
\(4^{2k}\)为其最高阶无穷大
i取k，得\(T(4^k)=2^kT(4^0)+2^{k-1}*4^{0}+...+4^{2k}\)
\(lim\)\(T(4^k) \over 4^{2k}\) = 1 = \(lim\)\(T(n) \over n^2\)
故时间复杂度为\(O(n^2)\)
某算法的时间复杂度可用递归式
\[T(n)= \begin{cases} O(1)& \text{n=1}\\ 2T(n/2)+nlgn& \text{n>1} \end{cases}\]
表示，若用O表示该算法的渐进时间复杂度的紧致界，则时间复杂度为？
-
迭代法：
- 只考虑 n=\(2^k\) 的子列,换元之后把 T(\(2^k\)) 记成 S(k),那么
\(S(k) = 2S(k-1) + 2^k * k\)
\(S(k-1) = 2S(k-2) + 2^{k-1} * (k-1)\)
...
\(S(1) = 2S(0) + 2\) - 把左端为 S(k-j) 的式子乘上 \(2^j\) 之后全加起来就消去了所有中间项得到
\(S(k) = 2^k S(0) + 2^k[k+(k-1)+...+1] = 2^k*O(1) + 2^k*Θ(k^2) = Θ(2^k*k^2)\) - 写成 T(n) 的形式就是 \(T(n)=Θ(n*(ln n)^2)\)
由于 T(n) 是单调的,考虑上述子列足够推出渐进量级了
- 只考虑 n=\(2^k\) 的子列,换元之后把 T(\(2^k\)) 记成 S(k),那么
某算法的时间复杂度可用递推式
\[T(n)= \begin{cases} O(1)& \text{n=1}\\ 6T(n/5)+n& \text{n>1} \end{cases}\]
表示，则时间复杂度为？
-
迭代法：
- 同样的方法,令 n=\(5^k\),那么
\(S(k) = 6S(k-1) + 5^k\)
\(S(k-1) = 6S(k-2) + 5^{k-1}\)
...
\(S(1) = 6S(0) + 5\) - 把左端为 S(k-j) 的式子乘上 \(6^j\) 之后全加起来就消去了所有中间项得到
\(S(k) = 6^k S(0) + [5^k + 6*5^{k-1} + ... + 6^{k-1}*5]\)
\(= 6^k*Θ(1) + 5*Θ(6^k) = Θ(6^k)\)
注意后面那堆求和是等比数列求和 - 换回去就得到 \(T(n) = Θ(n^{ln6/ln5})\)
- 同样的方法,令 n=\(5^k\),那么
某算法的计算时间为：T(n) = 4T(n/2) + O(n)，其中 T(1) = O(1)，求其时间复杂
度，写出具体过程。
设n=2^k，则T(n)=T(2^k)
令S(k)=T(2^k)
\[ \begin{align} S(k) &= 4^kS(0)+O(2^k)+4O(2^{k-1})+...+4^{k-1}O(2) \\ &= 4^kO(1)+2^k+2^{k+1}+...+2^{2k-1} \\ &= 4^k+4^k-2^k \\ &= O(n^2) \end{align} \]
后面一大串其实是等比数列。
