把每层执行次数乘起来，即可粗略得出时间复杂度。



答案
O(n5)O(n^5)O(n5)



4、求下列程序时间复杂度

count = 0
for (int i = N; i > 0; i /= 2)
for (int j = 0; j < i; j++)count++;

解析
这是道易错题。有些人会认为最外层循环执行了logNlogNlogN次，最内层NNN次，所以总时间复杂度为O(NlogN)O(NlogN)O(NlogN)次。这就是经典的错误~


正解：

考虑下count++会运行多少次：
当i=N时，它将运行N次。
当i=N/2时，它将运行N/2次。
当i=N/4时，它将运行N/4次。
以此类推···

因此，count++总共会运行N+N/2+N/4+...+1=2*N次。因此时间复杂度为O(N)O(N)O(N)。



答案
O(N)O(N)O(N)



5、其中n为正整数，则最后一行的语句频度在最坏的情况下为:

for(int i = n - 1; i >= 1; --i)for(int j = 1; j <=	i; ++j)if(A[j] > A[j + 1]) swap(A[j], A[j + 1]);

解析
冒泡排序，最坏情况下相当于两个for循环跑满，故为O(n2)O(n^2)O(n2)



答案
O(n2)O(n^2)O(n2)



6、(2019·华中科技大学) 什么是时间复杂度？
解析略

7、求下列程序时间复杂度

int a = 0;
for (i = 0; i < N; i++) {for (j = N; j > i; j--) {a = a + i + j;}
}

解析
外层共执行N-1次，内层每次执行N - i次。因此可以列出式子：
∑i=0N−1(N−i)=∑i=0N−1N−∑i=0N−1i=N2−N(0+N−1)2=12N2+12N≈O(N2)\sum\limits^{N-1}_{i=0}(N-i)=\sum\limits^{N-1}_{i=0}N-\sum\limits^{N-1}_{i=0}i=N^2-\frac{N(0+N-1)}{2}=\frac{1}{2}N^2+\frac{1}{2}N \approx O(N^2)i=0∑N−1​(N−i)=i=0∑N−1​N−i=0∑N−1​i=N2−2N(0+N−1)​=21​N2+21​N≈O(N2)



答案
O(N2)O(N^2)O(N2)



8、求下列程序时间复杂度

void fun(int n){int i = 0;while(i * i * i <= n)i++;
}

解析
i++是基本运算，整体上不会改变循环的时间复杂度，故忽略不计；由t*t*t≤n，得到结果是O(n3\sqrt[3]{n}3n​)



答案
O(n3\sqrt[3]{n}3n​)



9、求 “m++” 执行次数

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

解析
可以列出式子：
∑i=1n∑j=12i1=∑i=1n2i=2∑i=1ni=2n(n+1)2=n(n+1)\sum\limits^n_{i=1}\sum\limits^{2i}_ {j=1}1=\sum\limits^{n}_{i=1}2i=2\sum\limits^{n}_{i=1}i=2\frac{n(n+1)}{2}=n(n+1)i=1∑n​j=1∑2i​1=i=1∑n​2i=2i=1∑n​i=22n(n+1)​=n(n+1)



答案
n(n+1)



10、求下列程序时间复杂度

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

解析
递归算法的时间复杂度: 递归次数 * 每次递归中的操作次数
这里每次调用递归参数减1，故一共执行了n次递归调用。



答案
O(n)O(n)O(n)



11、求下列程序时间复杂度

int func(int n){int i = 0, sum = 0;while(sum < n) sum += ++i;return i;
}

解析
列举一些算式来找规律：
由sum += ++i，得sum = sum + ++i
接着设t为循环执行的次数，则：

t=1时, sum = 0 + ++i = 0 + 1;
t=2时, sum = 0 + 1 + ++i = 0 + 1 + 2;
t=3时, sum = 0 + 1 + 2 + ++i = 0 + 1 + 2 + 3;

于是可以推出sum值计算式为：
t=k时, sum = 0 + 1 + 2 + ··· + ++(k-1) = 0 + 1 + 2 + ··· + k=k(1+k)/2
因为sum < n是终止循环的条件，所以我们令k(1+k)/2 < n，即
k(1+k)2 计算过程此处不赘述，结果忽略掉常数项，保留n那一项就行。
解得 k = n12n^{\frac{1}{2}}n21​
故时间复杂度为O(n12n^{\frac{1}{2}}n21​)



答案
O(n12n^{\frac{1}{2}}n21​)



12、求下列程序时间复杂度

for(int i = 1; i <= n; i++)for(int j = 1; j <= i; j++)for(int k = 1; k <= j; k++)x++;

解析
计算过程中用到了等差数列求和公式以及平方和公式：
O(∑i=1n∑j=1i∑k=1j1)=∑i=1n∑j=1ij=∑i=1ni(1+i)2=12∑i=1n(i+i2)=12((1+n)n2+n(n+1)(2n+1)6)=6n2−2n3+n+112≈O(16n3)≈O(n3)O(\sum\limits^{n}_{i=1}\sum\limits^{i}_{j=1}\sum\limits_{k=1}^{j}1)=\sum\limits^{n}_{i=1}\sum\limits^{i}_{j=1}j=\sum\limits^{n}_{i=1}\frac{i(1+i)}{2}=\frac{1}{2}\sum\limits^{n}_{i=1}(i+i^2) =\frac{1}{2}(\frac{(1+n)n}{2}+\frac{n(n+1)(2n+1)}{6}) =\frac{6n^2-2n^3+n+1}{12} \approx O(\frac{1}{6}n^3) \approx O(n^3)O(i=1∑n​j=1∑i​k=1∑j​1)=i=1∑n​j=1∑i​j=i=1∑n​2i(1+i)​=21​i=1∑n​(i+i2)=21​(2(1+n)n​+6n(n+1)(2n+1)​)=126n2−2n3+n+1​≈O(61​n3)≈O(n3)



答案
O(n3)O(n^3)O(n3)

2 求递归式时间复杂度

1、一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别(下式中，n是问题的规模，n为2的整数次幂)

T(n) = {1,n=12T(n/2)+n,n>1\begin{cases}1, n=1 \\2T(n/2)+n, n>1 \end{cases}{1,n=12T(n/2)+n,n>1​

解析
对于递归程序求时间复杂度，有许多方法进行求解，如master定理、递归树、递推法等。
这里使用递推法来解题：
首先根据题意，得到①式：
T(n)=2T(n2)+n⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅①T(n)=2T(\frac{n}{2})+n ··············①T(n)=2T(2n​)+n⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅①
接着用扩展递归技术将递推式进行扩展，即令n=n/2得到②式：
=2T(n22)+n2⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅②=2T(\frac{\frac{n}{2}}{2})+\frac{n}{2}·············②=2T(22n​​)+2n​⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅②
再将②式代入①式，得到③式：
T(n)=2(2T(n22)+n2)+n⋅⋅⋅⋅⋅⋅⋅③T(n)=2(2T(\frac{\frac{n}{2}}{2})+\frac{n}{2})+n·······③T(n)=2(2T(22n​​)+2n​)+n⋅⋅⋅⋅⋅⋅⋅③
接着重复②③式的计算步骤：
=T(n)=2T(n/2)+n=T(n)=2T(n/2)+n =T(n)=2T(n/2)+n
=22T(n22)+2n=2^2T(\frac{n}{2^2})+2^n=22T(22n​)+2n
.........
当k=log2nk=log_2nk=log2​n时，递归结束，此时即为最终的递推式：
T(n)=2log2nT(1)+nlog2nT(n)=2^{log_{2}n}T(1)+nlog_2nT(n)=2log2​nT(1)+nlog2​n
=n(log2n+1)=n(log_2n+1)=n(log2​n+1)
=O(nlog2n)=O(nlog_2n)=O(nlog2​n)



答案
O(nlog2n)O(nlog_2n)O(nlog2​n)

补充

扩展递归技术是一种求解递推关系式的方法。它的作用是将递推关系式中等式右边的项根据递推式替换，这称为扩展，扩展后的项被再此扩展，依次下去，就会得到一个求和表达式。这样可以方便地计算出递归算法的时间复杂度。

2、一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别

T(n) = {1,0≤n≤12T(n−1)+1,n>1\begin{cases}1, 0≤n≤1 \\2T(n-1)+1, n>1 \end{cases}{1,0≤n≤12T(n−1)+1,n>1​

解析
递推法：
由T(n)=2T(n-1)+1，于是推出
T(1)=2T(0)+1=20+20−1T(1)=2T(0)+1=2^0+2^0-1T(1)=2T(0)+1=20+20−1
T(2)=2T(1)+1=21+21−1T(2)=2T(1)+1=2^1+2^1-1T(2)=2T(1)+1=21+21−1
T(3)=2T(2)+1=22+22−1T(3)=2T(2)+1=2^2+2^2-1T(3)=2T(2)+1=22+22−1
.........
T(n)=2T(n−1)+1=2n−1+2n−1−1=2n−1T(n)=2T(n-1)+1=2^{n-1}+2^{n-1}-1=2^n-1T(n)=2T(n−1)+1=2n−1+2n−1−1=2n−1
保留最高次项，最终得：T(n)=2n−1=O(2n)T(n)=2^n-1=O(2^n)T(n)=2n−1=O(2n)



答案
O(2n)O(2^n)O(2n)



3、分析递归与非递归算法下，斐波那契数列的时间复杂度

F(n) = {0,n=01,n=1F(n−1)+F(n−2),n>1\begin{cases}0, n=0 \\1, n=1 \\F(n-1)+F(n-2), n>1 \end{cases}⎩⎨⎧​0,n=01,n=1F(n−1)+F(n−2),n>1​

递归算法

int Fib1(long long num){ if ((num == 1) || (num == 0)){ return num; } return Fib1(num-1)+Fib1(num-2); 
} 

解析
搞清楚了再回来填坑 (´ο｀)

答案


非递归算法：

int Fib(int n) {if (n == 0) return 0;if (n == 1) return 1;int a = 0, b = 1;for (int i = 2; i <= n; i++) {int temp = a + b;a = b;b = temp;}return b;
}

解析
非递归算法只需用到一个循环。用两个变量来存储前两项的值，用一个循环来更新它们。



答案
O(n)O(n)O(n)

4、如下函数 mergesort() 执行的时间复杂度为多少?
假设函数调用被写为mergesort(1,n)，函数 merge() 的时间复杂度为O(n)O(n)O(n)

void mergesort(int i, int j){int m;if(i != j){m = (i + j) / 2;mergesort(i, m);mergesort(i + 1, j);merge(i, j, m);  //这一句函数复杂度为O(n)}
}

解析

答案
O(nlog2n)O(nlog_2n)O(nlog2​n) or O(nlogn)O(nlogn)O(nlogn)
两种写法是等价的，均为正确

5、一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别

T(n) = {3T(n−1),n>01,otherwise\begin{cases}3T(n-1), n>0 \\1, otherwise \end{cases}{3T(n−1),n>01,otherwise​

解析
根据递归式展开：
T(n)=3T(n−1)T(n)=3T(n-1)T(n)=3T(n−1)
=3(3T(n−2))= 3(3T(n-2)) =3(3T(n−2))
=32T(n−2)= 3^2T(n-2)=32T(n−2)
=33T(n−3)= 3^3T(n-3)=33T(n−3)
…… …
=3nT(n−n)= 3^nT(n-n)=3nT(n−n)
=3nT(0)=3n= 3^nT(0) = 3^n=3nT(0)=3n



答案
O(3n)O(3^n)O(3n)



6、一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别

T(n) = {2T(n−1)–1,n>0,1,otherwise\begin{cases}2T(n-1) – 1, n>0, \\1, otherwise \end{cases}{2T(n−1)–1,n>0,1,otherwise​

解析
  展开递归式,计算前几项的值，你会发现每个式子结果都等于1：
T(n)=2T(n−1)–1=1T(n) = 2T(n-1) – 1=1T(n)=2T(n−1)–1=1
=22(T(n−2))–2–1=1= 2^2(T(n-2)) – 2 – 1=1=22(T(n−2))–2–1=1
=23(T(n−3))–22–21–20=1= 2^3(T(n-3)) – 2^2 – 2^1 – 2^0=1=23(T(n−3))–22–21–20=1
………
因此时间复杂度就是O(1)O(1)O(1)。
  注意，虽然本题一眼看上去递归关系是指数的，但通过展开递归关系式，得到了完全不同的结果。因此在处理这类问题的时候，最好能把递归式展开再确定时间复杂度。



答案
O(1)O(1)O(1)

附送一张壁纸ヽ(^ｰ^)人(^ｰ^)ノ