目录
- 1 求时间复杂度
- 2 求递归式时间复杂度
前言
本文用于练习时间复杂度求解,共20+题,难度适中,题目来源为考研教辅书以及网上搜集,如有错误请指出,会第一时间进行修改。
1 求时间复杂度
1、求下列程序时间复杂度
void function(int n)
{if (n==1)return;for (int i=1; i<=n; i++){for (int j=1; j<=n; j++){cout << "*";break;}cout << endl;}
}
解析
别把内层的break看漏了
答案
O(n)O(n)O(n)
2、求下列程序时间复杂度
void function(int n)
{int count = 0;for (int i=n/2; i<=n; i++)for (int j=1; j<=n; j = 2 * j)for (int k=1; k<=n; k = k * 2)count++;
}
解析
void function(int n)
{int count = 0;// 执行 n/2 次for (int i=n/2; i<=n; i++)// 执行 n/2 次for (int j=1; j+n/2<=n; j = j++)// 执行 logn 次for (int k=1; k<=n; k = k * 2)count++;
}
因此结果就是三个层的时间复杂度相乘。
答案
O(n2logn)O(n^2logn)O(n2logn)
3、求下列程序时间复杂度
void function(int n)
{int count = 0;for (int i=0; i<n; i++)for (int j=i; j< i*i; j++)if (j%i == 0){for (int k=0; k<j; k++)printf("*");}
}
解析
void function(int n)
{int count = 0;// 执行 n 次for (int i=0; i<n; i++)// 执行 O(n*n) 次for (int j=i; j< i*i; j++)if (j%i == 0){// 执行 j 次 = O(n*n) 次for (int k=0; k<j; k++)printf("*");}
}
把每层执行次数乘起来,即可粗略得出时间复杂度。
答案
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−1N−i=0∑N−1i=N2−2N(0+N−1)=21N2+21N≈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∑nj=1∑2i1=i=1∑n2i=2i=1∑ni=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\frac{k(1+k)}{2} < n2k(1+k)<n
计算过程此处不赘述,结果忽略掉常数项,保留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∑nj=1∑ik=1∑j1)=i=1∑nj=1∑ij=i=1∑n2i(1+i)=21i=1∑n(i+i2)=21(2(1+n)n+6n(n+1)(2n+1))=126n2−2n3+n+1≈O(61n3)≈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=log2n时,递归结束,此时即为最终的递推式:
T(n)=2log2nT(1)+nlog2nT(n)=2^{log_{2}n}T(1)+nlog_2nT(n)=2log2nT(1)+nlog2n
=n(log2n+1)=n(log_2n+1)=n(log2n+1)
=O(nlog2n)=O(nlog_2n)=O(nlog2n)
答案
O(nlog2n)O(nlog_2n)O(nlog2n)
补充
扩展递归技术是一种求解递推关系式的方法。它的作用是将递推关系式中等式右边的项根据递推式替换,这称为扩展,扩展后的项被再此扩展,依次下去,就会得到一个求和表达式。这样可以方便地计算出递归算法的时间复杂度。
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(nlog2n) 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)
附送一张壁纸ヽ(^ー^)人(^ー^)ノ