Monodyee

这个屌丝很懒，什么也没留下！

热门标签

【考研】时间复杂度与空间复杂度习题练习（含真题）_试分析下列各算法的时间复杂度

作者：Monodyee | 2024-04-17 12:41:35

踩

试分析下列各算法的时间复杂度

前言

题目主要是选取自408考研真题、《数据结构（C语言版）》严蔚敏编著的教材课后习题、王道习题等。

如有错误，请在评论区讨论指正。

前言

一、时间复杂度

二、空间复杂度

一、时间复杂度

1、试分析下列各算法的时间复杂度。


// (1)
x = 90; y = 100;
while(y > 0){
    if(x > 100){
        x = x - 10;
        y--;
    }else{
        x++;
    }
}

（1）解：运行程序，有 x < 100, x = 91 ...... x = 101时，有 x = 91, y = 99，每循环11次y的值减1，所以总循环次数有11 * 100 = 1100。

所以，时间复杂度：O(1) ，因为程序的执行次数为常数阶。


//（2）
for (i = 0; i < n; i++)
      for (j = 0; j < m; j++)
         a[i][j] = 0;

（2）解：语句 a[i][j] = 0; 执行次数有 $\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} 1 =\sum_{i=0}^{n-1}(m-1)$ ，可推出执行次数为 m * n 次。

所以时间复杂度为 O(m*n)。


// （3）
s = 0;
for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
         s += B[i][j];
sum = s;

（3）解：语句 s += B[i][j]; 的执行次数为 n * n 。

所以，时间复杂度为 $O(n^2)$ 。


//（4）
i = 1;
while(i <= n)
    i = i*3;
 
/* //推导可知：
i = 1;
while(i <= n)
    i = i*2;
//时间复杂度为O(logn)，底数为2。
*/

（4）解： i 的值为：1，3，9， 27，...

用 i(x) 表示第 x 次循环时i的值，则 $i(x) = 3^x$ , x初始值为0。

语句 i = i*3; 的执行次数为 $3^x \leq n$ ，有 $x \leq log_3n$

所以，时间复杂度为 $O(log_3n)$ 。


//（5）
x = 2;
while(x < n/2)
    x = x * 2;

（5）解：x 的取值是首项为4，公比为2的等比数列，

设执行次数为 t，则有 $2^{t+1}<\frac{n}{2}$ ，即 $t<log_2{\frac{n}{2}}-1$

所以，时间复杂度为 $O(log_2n)$ 。


//（6）
x = 0;
for(i = 1; i < n; i++)
    for (j = 1; j <= n-i; j++)
        x++;

（6）解：语句x++; 的执行次数为 $\sum_{i=1}^{n-1}\sum_{j=1}^{n-i} 1 =\sum_{i=1}^{n-1}(n-i) = (n-1)+(n-2)+(n-3)+...+2 + 1 = \frac{(n-1)n}{2}$

所以，时间复杂度为 $O(n^2)$ 。


//（7）
x = 0;
for(k = 1; k <= n; k*=2)
    for (j = 1; j <= n; j++)
        x++;

（7）解：此题不同于（6）小题，内层循环条件 j <= n 与外层循环变量无关。

每执行一次 j 自增一，每次内层循环都执行 n 次，所以内层的时间复杂度为 O(n)。

对于外层，设循环次数 t 满足 $k=2^t\leq n$ ，所以， $t\leq log_2n$ 。

所以，内层的时间复杂度*外层的时间复杂度即为 $O(n)*O(log_2n)=O(nlog_2n)$

所以，时间复杂度为 $O(nlog_2n)$ 。


//（8）
int fact(int n){
    if(n <= 1)
        return 1;
    return n*fact(n-1);
}

（8）解：本题是求 n 的阶乘，即 n(n-1)(n-2)*...*2*1，

每次递归调用时 fact() 的参数减一，递归出口为 fact(1)，一共执行 n 次递归调用 fact()，

所以，时间复杂度为 O(n) 。


//（9）
x = n;     //n>1
y = 0;
while(x ≥ (y+1) * (y+1))
    y++;

（9）解：语句 y++; 的执行次数为 $n \geq (y+1) * (y+1))$ ，有 $y \leq n^{\frac{^{1}}{2}}-1$ 。

所以，时间复杂度为 $O(n^{\frac{1}{2}})$ 。


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

（10）解：i 与 sum 的取值变化如下：

i	sum
1	0+1
2	0+1+2
3	0+1+3
...	...
ｔ	$0+1+2+3+...+t = \frac{t(1+t)}{2}$

所以，有 $\frac{t(1+t)}{2}<n\Rightarrow \frac{t^2}{2}<n\Rightarrow t<\sqrt{2n}$

所以，时间复杂度为 $O(n^{\frac{1}{2}})$ 。


//（11）
for(int i= n-1; i > 1; i--)
	for (int j = 1; j < i; j++) 
		if(A[j] > A[j+1])
			A[j]与A[j+1]对换;

（11）解：最后一行语句频度在最坏情况下是 $O(n^2)$ 。

当所有相邻元素都为逆序时，则最后一行的语句每次都会执行。

则有 $\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}1=\sum_{i=2}^{n-1}(i-1)=\frac{(n-2)(n-1)}{2}$

所以，时间复杂度为 $O(n^2)$ 。

2、已知两个长度分别为 m 和 n 的升序链表，若将它们合并为长度为 m + n 的一个降序链表，则最坏情况下的时间复杂度是 O(max(m,n))。

解：两个升序链表合并，两两比较表中元素，每比较一次，确定一个元素的链接位置（取较小元素）。当一个链表比较结束后，将另一个链表的剩余元素插入即可。

最坏的情况是两个链表中的元素依次进行比较，因为2 max(m,n) >= m + n，所以时间复杂度为O(max(m,n))。

二、空间复杂度

1、试分析以下算法的空间复杂度。


// (1)
int j = 0;
for (int i = 0; i < n; i++) {
    j++;
}

（1）解：随着 n 的变化，所需开辟的内存空间并不会随着 n 的变化而变化，

所以，空间复杂度 O(1)。


//（2）
int fun(int n){
    int x = 100;
    if（n == x)
        return n;
    else
        return fun(++n);
}

（2）解：此题是递归调用fun函数，随着 n 的变化，所需开辟的内存空间会随着 n 的变化而变化，所以，空间复杂度 O(n)。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/440247