算法分析典型例题

Question

本文是关于算法分析的一些例题，主要前段时间有重温一下算法中时间复杂度的计算，因此也记录了一些简单的例题，比较基础，但是也做个记录吧。每个题目都是需要分析下所涉及算法的复杂度，话不多说，直接开始吧。

题 1

分析以下各程序段，求出算法的时间复杂度

i=1;k=0;
while (i<n-1) {
 k=k+10*1:
 i++;}

题解：

1. i++是可以影响 while 的，循环一次 i 就加一，直到 i=n-1 跳出循环。一共循环了 n-2 次
2. 所以时间复杂度是 O（n）

题 2

分析以下各程序段，求出算法的时间复杂度

y=0
while ((y+1)*(y+1)<=n)
 y=y+1;

题解：

1. y=y+1 是可以影响 while 的, 循环一次 y 就加一，直到 (y+1)^2 > n 跳出循环。
2. y= n^(1/2)-1, 所以时间复杂度为 O(n^(1/2))

题 3

分析以下各程序段，求出算法的时间复杂度

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

题解：

1. 这是三个嵌套的循环，首先我们观察最内部的 k，k 的范围是（1，x），一共执行了 x 次。
2. 然后 j，j 的范围是（1，n），一共执行了 n 次，
3. 最后观察最外部的 i，i 的范围是（1，m），一共执行了 m 次。
4. 只需把三个变量的循环次数相乘就能得到最终的时间复杂度 O(mnx).

题 4

分析以下各程序段，求出算法的时间复杂度

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

题解：

1. 内层循环条件 j <=n 与外层循环变量无关。每执行一次 j 自增一，每次内层循环都执行 n 次，所以内层的时间复杂度为 O(n)。
2. 对于外层，设循环次数 t 满足 k=2^t <= n, 所以 t<= log(n).
3. 所以，内层的时间复杂度*外层的时间复杂度即为 O(n)*O(log(n))=O(nlog(n)), 所以时间复杂度为 O(nlog(n))。

题 5

分析以下各程序段，求出算法的时间复杂度

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

题解：

1. 第一个 for 循环，执行次数是 n，所以时间复杂度是 O(n).
2. 第二个 for 循环，内层 j 的范围是（1，n）一共执行了 n 次，外层 i 的范围是（1，n）一共执行了 n 次，第二个 for 循环的时间复杂度是 O(n^2).
3. 总共的时间复杂度是第一个 for 循环的时间复杂度加上第二个 for 循环的时间复杂度，O(n)+O(n^2)=O(n^2), 所以时间复杂度为 O(n^2).

题 6

分析以下各程序段，求出算法的时间复杂度

// A[]、B[]两个数组为升序数组
i=0,j=0,k=0;
while(i<n && j<n){
	if(A[i] < B[j]){
		C[k]=A[i];
		i = i+1;
	}
	else if(A[i] > B[j]){
		C[k]=B[j];
		j=j+1;
	}
	else{
		C[k]=A[i];
		i = i+1;
		j=j+1;
	}
}

if (i<n){
	for (int s = i; s < n; ++s){
		C[s] = A[n-s-1];
	}
	k = k+n-i
}
if (j<n){
	for (int s = j; s < n; ++s){
		C[s] = A[n-s-1];
	}
	k = k+n-j
}

题解：

1. 两个数组都是升序的数组，根据代码分析，我们只需把数组 X 和数组 Y 中的每个元素依次进行对比，选出最小的元素放到数组 Z 中，对于相同大小的元素，就把数组 X 的元素放到数组 Z 中即可。
2. 需要对比两个数组中的全部元素，需要运行 2n 次，时间复杂度就是 O(n).

题 7

数组集 X 和数组集 Y 每个数组集中都有 k 个数组，(X(1)，X(2)…X(k-1)，X(k)),(Y(1),Y(2),Y(3)……Y(k-1),Y(k))
对于数组集 X 中每个数组都有相同的元素个数 m，数组集 X 中每个数组都有相同的元素个数 n，并且每个数组都是升序数组。我们想把两个数组集中的数组通过上面的算法进行合并。直至剩下一个数组。
第一步 X(1) 和 Y(1) 进行合并，X(2) 和 Y(2) 进行合并……X(k) 和 Y(k) 进行合并,反复对比只留下最后一个数组,最后一步（X(1)，Y(1)）和（X(2)，Y(2)）进行对比……（X(k-1)，Y(k-1)）和（X(k)，Y(k)）进行对比直到剩下最后一个数组。请计算时间复杂度，并且解释。

题解：

第一步：时间复杂度 O(m+n)*k=O((m+n)*k)
因为两个数组组合所以是 m+n，并且因为有 k 对数组所以运行了 k 次，相乘就是第一步的时间复杂度

第二步：时间复杂度 O(2m+2n)*MAX(k/2)=O((m+n)*k)
这一步相当于四个数组组合所以元素个数是 2(m+n)，并且这个时候的数组对又减少了一半变成了 MAX(k/2)，相乘就是第二步的时间复杂度.

第三步：时间复杂度 O(4m+4n)*MAX(k/4)=O((m+n)*k)
这一步相当于八个数组组合所以元素个数是 4(m+n)，并且这个时候的数组对又减少了一半变成了 MAX(k/4)，相乘就是第三步的时间复杂度

…

第 log(2k) 步（最后一步)：时间复杂度 O((k)(m+n))*1=O((m+n)*k)
这一步相当于把所以的数组都合并到一个数组中，所有的元素个数是(k)(m+n)，运行了一次，(相当于两个数组合并成一个数组)，相乘就是第二步的时间复杂度

由此看见每一步的时间复杂程度都是 O((m+n)*k)，但是一共有 log(2k) 步，所以最终的时间复杂度是 O((m+n)*k*log(2k))。

题 8

分析以下各程序段，求出算法的时间复杂度

for (i=1;i<n;i++){
 y=y+1; 
 for (j=0;j<=(2*n);j++)     
  x++; 
}

题解：

1. 算法中主要语句 y=y+1 的时间复杂度为 O(n+1)=O(n)
2. 算法中主要语句 (j=0;j<=(2*n);j++) 的时间复杂度为 O((n+1)*(2n+1)) = O(n^2).
3. 因此，本算法的时间复杂度为 O(n+1) + O((n+1)*(2n+1)) = O(n) + O(n^2) = O(n^2).

题 9

分析以下各程序段，求出算法的时间复杂度

// 求两个 n 阶矩阵的的乘法 C=A✖B，其算法如下：
#define MAX 100
Void matrixmult (int n, float a[MAX] [MAX], float c[MAX] [MAX]){
    int i, j, k;
    float x;
    for (i=1; i<=n; i++){
      for (j=1; j<=n; j++){
 		x=0;
 		for (k=1; k<=n; k++)
        	x+= a[i] [k]* b[k] [j]
        	c[i] [j]=x;
      	}//for (j=1) 结束
	}//for (i=1) 结束
}// matrixmult

题解：

1. 算法中主要语句 for (i=1;i<=n;i++) 的时间复杂度为 O(n+1)=O(n)
2. 算法中主要语句 for (j=1;j<=n;j++) 的时间复杂度为 O(n*(n+1)) = O(n^2).
3. 算法中主要语句 x=0 的时间复杂度为 O(n^2).
4. 算法中主要语句 for (k=1;k<=n;k++) 的时间复杂度为 O(n^2*(n+1)) = O(n^3).
5. 算法中主要语句 x+=a[i][k]*b[k][j] 的时间复杂度为 O(n^3).
6. 算法中主要语句 c[i][j]=x 的时间复杂度为 O(n^2).
7. 因此，本算法的时间复杂度为 O(n+1)+O(n*(n+1))+O(n^2)+O(n^2*(n+1))+O(n^3)+O(n^2) = O(n)+O(n^2)+O(n^2)+O(n^3)+O(n^3)+O(n^2) = O(n^3)

题 10

有两个算法 A1 和 A2 求解同一问题，时间复杂度分别是 O1(n)=100n^2，O2(n)=5n^3。 评估这两个算法的时间性能

题解：

1. 当输入量 n ＜20 时，有 T1(n)＞T2(n)，后者花费的时间较少。
2. 随着问题规模 n 的增大，两个算法的时间开销之比 5n^3/100n^2=n/20 亦随着增大。即当问题规模较大时，算法 A1 比算法 A2 要有效地多。 它们的渐近时间复杂度 O(n^2) 和 O(n^3) 从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度 O(n)=O(f(n)) 简称为时间复杂度，其中的 f(n) 一般是算法中频度最大的语句频度。