时间复杂度计算方法

时间复杂度的计算

例子

for (i = 0; i < n; i++)
{
	for (j = 0; j < n; j++)
	{
		printf("csdn");
	}
}		
1
2
3
4
5
6
7

从这可以看出这个算法时间的复杂度为n²（O(n²)）

for (i = 0; i < n; i++)
{
	for (j = i; j < n; j++)
	{
		printf("csdn");
	}
}
1
2
3
4
5
6
7

在计算时间复杂度时，省略较小的项，去掉常数，只保留最高阶。故这个算法的时间复杂度也是n²(O(n²))

for (i = 1; i < n; i *= 2)
{
	printf("csdn");
}
1
2
3
4

在计算语句执行次数时，会发现语句的执行次数与n的值和后面的i *= 2有关；而且可以发现他们的关系为以2为底的对数关系。可以发现执行次数 = log~2~n。
去掉常数2 。得到时间复杂度为logn（O(logn)）。

举一个简单的例子：
计算从i = 1开始，每次i增加1后的 i³的连续和；
(i = 1) (N)∑ i³

		int sum(int N)
		{
/*1*/		int i, partialSum = 0;
/*2*/		for (i = 0; i <= N; i++)
/*3*/			partialSum += i * i * i;
/*4*/		 return partialSum;
		}
1
2
3
4
5
6
7

第一行和第4行各占一个时间单元，第3行占4个时间单元（一次赋值，一次加法，两次乘法）

省略掉常数后，得到的时间复杂度为n （O(n)）。

计算的一般法则：

• for循环：
  一次for循环的运行时间之多是该for内语句（包括测试）的运行时间乘以迭代次数。
• 嵌套的for循环：
  从里到外分析这些循环。在一组嵌套内部的语句总的运行时间为该语句的运行时间乘以所有的for循环的大小乘积。
• 顺序结构：
  将各个语句的运行时间求和即可（这意味着最大值就是该算法的运行时间）

for(i = 0; i < N; i++)
	printf("csdn");
for (i = 0; i < N; i++)
	for (j = 0; j < N; j++)
		printf("scdn");
1
2
3
4
5

在这个语句中先去掉较小的O(N)， 在花费O(N²)，总的花销也就是O(N²)；

• if / else语句

if(Condition)
	S1;
else 
	S2;
1
2
3
4

一个if / else 语句的运行时间，从不超过判断的时间 加上 S1与S2中运行时间较长的总的运行时间。

分析的策略基本都是从内部（或者最深层次）向外扩展开的。如果有函数调用，那么这些函数调用要最先分析。

如果有递归过程，那么存在这么几种选择

• 如果这个递归只是实际上只是稍加掩饰的for循环。

例子：

long int 
factorial(int N)
{
	if (N <= 1)
		return 1;
	else 
		return N * factorial (N - 1);
}		
1
2
3
4
5
6
7
8

不难看出这个算法的时间的复杂度为O(N)。

long int 
Fib(int N)
{
	if (N <= 1)
		return 1;
	else 
		return Fib(N - 1) + Fib(N - 2);
}
1
2
3
4
5
6
7
8

可以证明($\frac{5}{3}$)^N >= Fib(N) >= ($\frac{3}{2}$)^N
这个时间复杂度是个指数，是最坏的情况。违反了第四条基本法则。
注释：递归调用的四条基本法则

1. 基准情形。必须有某些基准的情形，他们不用递归就能求解。
2. 不断推进。对于那些递归求解的情形，递归调用必须能够朝着产生基准情形的方向推进。
3. 设计法则。假设所有的调用都能运行。
4. 合成效益法则。在求解一个问题的同一实例时，切勿在不同的递归中重复工作。

算法优化实例

最大子序列和

计算给出的一个数列中划分的各个子数列中最大的那个值。

int
MaxSubsequenceSum(const int A[], int N)
{
	int ThisSum, MaxSum, i, j, k;

	MaxSum = 0;
	for (i = 0; i < N; i++)
		for (j = i; j < N; j++)
		{
			ThisSum = 0;
			for (k = i; k <= j; k++)
			{
				ThisSum += A[K];
			}
			if (ThisSum > MaxSum)
			{
				MaxSum = ThisSum;
			}
		}
	return MaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

不难看出这个算法的时间复杂度为O(n³)
为我们可以进行一步优化，将最外部的循环删去会发现他并不会影响结果。因此可以得到：

int
MaxSubsequenceSum (const int A[], int N)
{
	int ThisSum, MaxSum, i, j;
	
	MaxSum = 0;
	for (i = 0; i < N; i++)
	{
		ThisSum = 0; 
		for (j = i; j < N; j++)
		{
			ThisSum += A[j];
			
			if (ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
	return MaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

新的算法的时间复杂度不难看出为O(n²)。在数列数字个数很多的时候显然这个新的算法更具有优势。
有时候递归和二分的运用能够大幅度的优化时间复杂度，在这里有一个很好的例子：

int 
Max3(int a, int b, int c)
{
	int max = 0;
	if (a > b)
		max = a;
	else 
		max = b;
	if (max > c)
		max = max;
	else 
		max = c;
	return max;
}
int
MaxSubSum(const int A[], int left, int Right)
{
	int MaxLeftSum, MaxRightSum; 
	int MaxLeftBorderSum, MaxRightBorderSum;
	int LeftBorderSum, RightBorderSum;
	int Center， i;
	
	if (Left == Right)
		if (A[Left] > 0)
			return A[Left];
		else 
			return 0;
	
	Center = (Left + Right) / 2; 
	MaxLeftSum = MaxSubSum(A, Left, Center);
	MaxRightSum = MaxSubSum(A, Center + 1, Right);

	MaxLeftBorderSum = 0; LeftBorderSum = 0; 
	for (i = center, i >= Left; i--)
	{
		LeftBorderSum += A[i];
		if (LeftBorder > MaxLeftBorderSum)
			MaxLeftBorderSum = LeftBorderSum;
	}
	
	MaxRightBorderSum = 0; RightBorderSum = 0; 
	for (i = center + 1; i <= Right; i++)
	{
		RightBorderSum += A[i];
		if (RightBorderSum > MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	}

	return Max3(MaxLeftSum, MaxRightSum, MaxLeftSum + MaxRightSum);
}
int 
MaxSubsequenceSum(cost int A[], int N)
{
	return MaxSubSum(A, 0, N - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

这段代码的在数量和复杂程度都超过了前两个算法，要设计这个算法是要花费一定的精力的，但是这段代码时间复杂度控制的很好，这个算法的时间复杂度就是O(nlogn)。

计算过程明天再加。