1 时间复杂度计算

约 908 个字 54 行代码 1 张图片预计阅读时间 4 分钟

常用的时间复杂度计算：

1 一层循环

i=n*n;
while(i!=1){
    i=i/2;
}

列出循环趟数 \(t\) 及每轮循环 \(i\) 的变化值：

t: 0 1 2 3 ...
i: \(n^2\) \(\frac{n^2}{2}\) \(\frac{n^2}{4}\) \(\frac{n^2}{8}\) ...

找到 \(t\) 与 \(i\) 的关系：
\(i=\frac{n^2}{2^t}\)
确定循环停止条件:
\(i=1\)
联立两式，解\(t\)
\(\frac{n^2}{2^t}=1\) \(n^2=2^t \Rightarrow t=2\log_2n\)
写结果，系数省略，即\(O(\log_2n)\)

例2：

x=0;
while (n>=(x+1)*(x+1))
    x=x+1;

解：
1. 列出 \(t\) 和 \(x\)：

t: 0 1 2 3 ...
x: 0 1 2 3 ...

找到 \(t\) 和 \(x\) 的关系：
\(t=x\)
确定循环停止条件：
\(n=(x+1)^2 \Rightarrow x= \sqrt{n}-1\)
联立两式，解\(t\)
\(t= \sqrt{n}-1\)
写结果，省略系数

\(O(\sqrt{n})\)

2 两层循环

列出外层循环中\(i\)的变化值
列出内层语句中的执行次数
求和，写结果

int m=0,i,j;
for(int i=1;i<=n;i++){
    for(j=1;j<=2*i;j++){
        m++;
    }
}

\(i\)	1	2	3	\(n\)
内层语句执行次数	2	4	6	\(2n\)
\(\therefore\) 求和：\(\frac{n(2+2n)}{2}=n(n+1)\)
\(\Rightarrow O(n^2)\)

例2：

for (i=0;i<n;i++)
    for (j=0;j<m;j++)
        a[i][j]=0;

解：

\(i\)	1	2	3	\(\cdots\)	\(n\)
内层语句执行次数	\(m\)	\(m\)	\(m\)	\(\cdots\)	\(m\)
求和：\(m \times n \ \ \ \ \therefore T=O(mn)\)

例3：

count=0;
for (k=1;k<=n;k*=2)
    for(j=1;j<=n;j++)
        count++;

\(k\)	1	2	4	\(\cdots\)	\(n\)
内层语句执行次数	\(n\)	\(n\)	\(n\)	\(\cdots\)	\(n\)

求和：\(n\log_2n\)

\(\therefore T=O(n\log_2n)\)

3 多层循环

for(i=0;i<=n;i++)
    for(j=0;j<=i;j++)
        for(k=0;k<j;k++)
            s++

解：

抽象为锥体体积

|215

列式求和：

\(\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^{j-1} 1 =\sum_{i=0}^n \sum_{j=0}^i (j-1-0+1)=\sum_{i=0}^n \sum_{j=0}^i j=\sum_{i=0}^n \frac{(i+1)i}{2}\)

\(=\frac{1}{2}\sum_{i=0}^n(i^2+i)=\frac{1}{2}\sum_{i=0}^n i^2+\frac{1}{2}\sum_{i=0}^n i = O(n^3)\)

4 递归

1 递推式分析

例1:

int fact(int n){
    if (n<=1)
        return 1;
    else
        return (n*fact(n-1));
}

设执行时间 \(T(n)\) ( \(n\) 相关的函数 )

递归出口：

if (n<=1)
    return 1;

没有循环，时间复杂度 \(O(1)\)

else
    return (n*fact(n-1));

\(n\rightarrow O(1)\)
fact(n-1)\(\rightarrow T(n-1)\)

\(\therefore T(n)=\begin{cases} O(1), \text{if} \ n\leq 1 \\ O(1)+T(n-1), \text{if} \ n>1 \end{cases}\)

下面：理解成高中求数列\(T_n\)的通项公式

\(T(n)-T(n-1)=O(1)\)
\(T(n-1)-T(n-2)=O(1)\)
\(\cdots\)
\(T(2)-T(1)=O(1)\)

\(\therefore T(n)-T(1)=(n-1)O(1)\)

我们又有\(T(1)=O(1) \Rightarrow T(n) = nO(1)=O(n)\)

例2：(常见的归并排序)

void mergesort(int i, int j){
    int m;
    if(i!=j){
        m=(i+j)/2;
        mergesort(i,m);
        mergesort(m+1,j);
        merge(i,j,m);
    }
}

其中两个mergesort是将[1,3,1,4,2,5,8,0]放进两个数组进行排序，之后再排序（merge）：
合并：[1,1,3,4] && [0,2,5,8]
0<1, 0 in
1<2, 1 in
...

\(n>1, T(n)=2T(\frac{n}{2})+O(n)\)

\(\therefore T(n) = 2T(\frac{n}{2})+cn\)

展开递归式直到基准情形：
\(\(\begin{align*} T(n) &= 2T\left(\frac{n}{2}\right) + cn \\ &= 2\left[2T\left(\frac{n}{4}\right) + c\cdot\frac{n}{2}\right] + cn = 4T\left(\frac{n}{4}\right) + 2cn \\ &= 4\left[2T\left(\frac{n}{8}\right) + c\cdot\frac{n}{4}\right] + 2cn = 8T\left(\frac{n}{8}\right) + 3cn \\ &\ \ \vdots \\ &= 2^k T\left(\frac{n}{2^k}\right) + k \cdot cn. \end{align*}\)\)
当 \(\frac{n}{2^k} = 1\)（即 \(k = \log_2 n\)）时，停止展开：
\(\(T(n) = n \cdot T(1) + cn \log_2 n\)\)
忽略常数项后，时间复杂度为 \(O(n \log n)\)。

习题：

(HW1) The Fibonacci number sequence {\(F_N\) } is defined as: \(F_0, F_1, F_N= F_{N-1}+F_{N-2}\) The time complexity of the function which calculates \(F_N\) recursively is \(\Theta (N!)\) (True or False)

Answer

False.

Method 1: 递归树是一棵二叉树，递归计算斐波那契数列的时间复杂度显然有上界\(O(2^N)\)
Method 2: 记住结论：\(O(1.5^N) \sim O(2^N)\)
实际上：\(\Theta((\frac{1+\sqrt{5}}{2})^ N) \approx \Theta(1.618^ N)\)

\(n^{0.01}\) is \(O(\log n)\). (True or False)

Answer

False.

直接记增长率的关系：\(n!>2^n>n^2>n \log n>n>n^{\alpha}>\log n>1\)
因此\(n^{0.01}\)一定会超过\(\log n\)

For the following piece of code:

if ( A > B ){     
  for ( i=0; i<N*2; i++ )         
    for ( j=N*N; j>i; j-- )             
      C += A; 
}
else {     
  for ( i=0; i<N*N/100; i++ )         
    for ( j=N; j>i; j-- ) 
      for ( k=0; k<N*3; k++)
        C += B; 
}

the lowest upper bound of the time complexity is \(O(N^3).\) (True or False)

Answer

False
如果A>B: \(N^2 \cdot 2N - \frac{(2N-1)2N}{2} \rightarrow O(N^3)\).
A<B:
\(\because\) 如果\(i\)比\(N\)大的话，没法进循环，所以\(i\)的最大值取\(N\)

\(i\)	0	1	2	\(\dots\)	\(N\)
\(j\)	\(3N \cdot N\)	\(3N(N-1)\)	\(3N(N-2)\)	\(\dots\)	0

\(\therefore 3N(N \cdot N-\frac{(N-1)N}{2})=\frac{3N^3+3N^2}{2} \Rightarrow O(N^3)\)

1 时间复杂度计算

1 一层循环

2 两层循环

3 多层循环

4 递归

1 递推式分析

Comments