本章内容：
算法的定义
算法(algorithm)为求解一个问题需要遵循的、被清楚指定的简单指令的集合。
ps：算法的几个特性这里就不赘述。
为了比较计算算法的性能，需要一些正式的系统架构来计算算法的性能，引入一些数学公式，用来比较：
注：
第一条定义的意义为T（N）的相对增长率小于等于f（N）的相对增长率。
第二条定义的意义为T（N）的相对增长率大于f（N）的相对增长率。
第三条定义的意义为T（N）的相对增长率等于f（N）的相对增长率。
第四条定义的意义为T（N）的相对增长率小于f（N）的相对增长率。
主要因素是所使用的算法以及该算法的输入。
一般来说，若无相反的指定，则所需要的量是最坏情况下的运行时间。
最大的子序列和问题
ps：恩，没错，这本书居然把这道经常考的面试题当做分析算法的讲解例题。
解法一：
1 int MaxSubSum(int A[], int N) 2 { 3 int ThisSum, MaxSum, i, j, k; 4 5 MaxSum = 0; 6 for (i = 0; i < N; i++) 7 for (j = i; j < N; j++) 8 { 9 ThisSum = 0; 10 for (k = i; k <= j; k++) 11 ThisSum += A[k]; 12 13 if (ThisSum > MaxSum) 14 MaxSum = ThisSum; 15 } 16 return MaxSum; 17 }
运行时间为O（N3），主要运行时间取决于三重循环。
解法二：
1 int MaxSubSum(int A[], int N) 2 { 3 int ThisSum, MaxSum, i, j; 4 5 MaxSum = 0; 6 for (i = 0; i < N; i++) 7 { 8 ThisSum = 0; 9 for (j = i; j < N; j++) 10 { 11 ThisSum += A[j]; 12 13 if (ThisSum > MaxSum) 14 MaxSum = ThisSum; 15 } 16 } 17 return MaxSum; 18 }
运行时间为O（N2），对第一这种方法进行了改进。
解法三：
1 int MaxSubSum(int A[], int Left, int Right) 2 { 3 int MaxLeftSum, MaxRightSum; 4 int MaxLeftBorderSum, MaxRightBorderSum; 5 int LeftBorderSum, RightBorderSum; 6 int center, i; 7 8 if (Left == Right) 9 if (A[Left] > 0) 10 return A[Left]; 11 else 12 return 0; 13 14 center = (Left + Right) / 2; 15 MaxLeftSum = MaxSubSum(A, Left, center); 16 MaxRightSum = MaxSubSum(A, center + 1, Right); 17 18 MaxLeftBorderSum = LeftBorderSum = 0; 19 for (i = center; i >= Left; i--) 20 { 21 LeftBorderSum += A[i]; 22 if (LeftBorderSum > MaxLeftBorderSum) 23 MaxLeftBorderSum = LeftBorderSum; 24 } 25 26 MaxRightBorderSum = RightBorderSum = 0; 27 for (i = center + 1; i <= Right; i++) 28 { 29 RightBorderSum += A[i]; 30 if (RightBorderSum > MaxRightBorderSum) 31 MaxRightBorderSum = RightBorderSum; 32 } 33 34 return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum); 35 }
运行时间为O（N*logN），该方法采用了分治的设计思想，运用递归进行实现。除了小输入外，一定会比前两个快。
值得一提的是分析该运行时间时运用到了学校上课讲的递推的思想，那我必须说一下了：
该算法的时间可以用一个线性时间O（N）加上两个求解子序列问题的时间。即
原文：http://www.cnblogs.com/selfimprovement/p/6257249.html
