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

• 基本步骤：
  1. a=?,b=?,f(n)=?，满足主定理条件
  2. f(n)的指数>(=)(<)\(log_ba\)，若大于，则判断cf(n)≥a(n/b),(c<1)
  3. 故时间复杂度为O(?)

• 题目：
  T(n)=3T(n/2)+\(n^2\)
• 思路：
  1. 试试能不能使用主方法，a=3,b=2,f(n)=n^2满足条件
  2. 看看满足哪一种情况，由于\(log_23\)<2，且\(3n^2/4 < cn^2\)(c<1)，满足第三种情况，所以T(n)=O(n^2)

迭代法

• 基本步骤：题目T(n) = aT(n/b) + f(n)
  1. 根据题目，设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)\)
  2. 将左端为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)\)
  3. 写成T(n)的形式，即S(k)=T(\(b^k\))=T(n)=...（其中k=\(log_bn\)），如：
     \(k=log_5n\)
     \(T(n) = Θ(n^{ln6/ln5})\)
• 题目：

//汉诺塔问题，假定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);
    }
}

• 思路：
  1. 首先写出表达式：T(n) = 2T(n-1)+O(1) （即 你的问题规模分解成了2个n-1的问题规模加上执行了一次基本操作move()
  2. 试试能不能使用主方法，发现a=2,b=1,f(n)=O(1),不满足b>1的条件，不能使用
  3. 采用迭代法，因为每次迭代n的数据规模减少1，到最后必然会有终点，即n==1。
     

     ---

     
     T(n)=2T(n-1)+1
     T(n-1)=2T(n-2)+1
     联立，得
     T(n)=4T(n-2)+1+2
     由数学归纳法，得
     T(n)=2^(n-1)T(1)+1+2+4+8+...+2^(n-2)
     又∵终止条件T(1)=1
     ∴时间复杂度为O(2^n)
     

     ---

综合例题

一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度级别。
\[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表示该算法的渐进时间复杂度的紧致界，则时间复杂度为？

• 迭代法：
  1. 只考虑 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\)
  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)\)
  3. 写成 T(n) 的形式就是 \(T(n)=Θ(n*(ln n)^2)\)
     由于 T(n) 是单调的,考虑上述子列足够推出渐进量级了

某算法的时间复杂度可用递推式
\[T(n)= \begin{cases} O(1)& \text{n=1}\\ 6T(n/5)+n& \text{n>1} \end{cases}\]
表示，则时间复杂度为？

• 迭代法：
  1. 同样的方法,令 n=\(5^k\),那么
     \(S(k) = 6S(k-1) + 5^k\)
     \(S(k-1) = 6S(k-2) + 5^{k-1}\)
     ...
     \(S(1) = 6S(0) + 5\)
  2. 把左端为 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)\)
     注意后面那堆求和是等比数列求和
  3. 换回去就得到 \(T(n) = Θ(n^{ln6/ln5})\)

某算法的计算时间为：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} \]

后面一大串其实是等比数列。