前言

题目主要是选取自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; 执行次数有   ，可推出执行次数为 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 。

所以，时间复杂度为  。

//（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的值，则 , x初始值为0。

语句 i = i*3; 的执行次数为 ，有 

所以，时间复杂度为  。

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

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

设执行次数为 t，则有  ，即 

所以，时间复杂度为  。

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

（6）解： 语句x++; 的执行次数为 

所以，时间复杂度为 。

//（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 满足 ， 所以，。

所以，内层的时间复杂度*外层的时间复杂度即为 

 所以，时间复杂度为  。

//（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++; 的执行次数为 ，有 。

 所以，时间复杂度为 。

//（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
...	...
ｔ

所以，有  

 所以，时间复杂度为 。

//（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）解：最后一行语句频度在最坏情况下是  。

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

则有 

 所以，时间复杂度为 。

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

​