算法分析

发表于   |   分类于   |  

数学基础

T(N)= O( f(N) ) T(N)的增长率 <= f(N)的增长率
T(N)= Ω( f(N) ) T(N)的增长率 >= f(N)的增长率
T(N)= θ( f(N) ) T(N)的增长率 = f(N)的增长率
T(N)= o( f(N) ) T(N)的增长率 < f(N)的增长率

一般法则

  1. 一次for循环运行时间至多是该for循环语句（包括）测试的运行时间乘以迭代的次数
  2. 嵌套的for循环。在一组嵌套循环内部的一条语句总的运行时间为该语句运行时间乘以该组所有for循环的大小
  3. 顺序语句。取最大的。

最大子序列为题

最先想到的是经过两次循环来遍历数组来确定最大的结果。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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; i < N; i++)
		{
			ThisSum += A[j];
			if(ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

时间效率是O(N^2)

下面介绍一种线性的算法，时间效率为O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
int MAXSubSequenceSum(const int A[], int N)
{
	int ThisSum, MaxSum, i;
	MaxSum = 0;
	for(i =0; i < N; i++)
	{
		ThisSum += A[i];
		if(ThisSum > MaxSum)
			MaxSum = ThisSum;
		else if(ThisSum < 0)
			ThisSum = 0;
	}
}

分析一下该算法。只遍历了一遍数组。（该算法的条件是数组必须含有非零整数）

1
2
else if(ThisSum < 0)
	ThisSum = 0;

这段代码解决了，不需要遍历两遍数组，在已知最大子序列值肯定是大于0的，把已经遍历的数，如果大于0，则继续遍历下去，以获取可能的最大的值。
如果小于0，说明后面的数要取得最大，不可能要加上前面全部的序列。如果只是截取前面的一部分呢？这个假设是不成立的。因为截取前面的一部分必须是正整数才有意义，但是如果是正整数，那么说明该部分的前面是负数，而且绝对值很大的负数，那再这之前就会因为小于0被淘汰掉。
综上所述，说明该算法是正确的。

运行时间中的对数

对分查找（binary search）

对预先给定好的已排序的数组，使用二分查找，能获得O(logN)的效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int BinarySearch(const int A[], int x ,int N)
{
	int low, mid, high;
	low = 0; high = N - 1;
	while(low <= high)
	{
		mid =(low + high) / 2;
		if(A[mid] > x)
			 high =mid - 1;
		else if(A[mid] < x)
			 low = mid + 1;
		else
			 return mid;
	}
	return -1;//not found
}

循环内所有花费是O(1),循环次数每次减半 默认情况下底数是2，所有效率是O(logN)

分析结果的准确性

经验指出，有时分析会估计过大。如果这种情况发生，要么需要分析得更细，要么可能就是平均运行时间显著小于最坏运行情况的运行时间。
对于许多复杂的算法，最坏的界可以通过某个不良输入可以达到，但是实践中通常是估计过大。