数据机构与算法分析读书笔记—

数据机构与算法分析读书笔记——算法分析

本章内容：

算法的定义
数学基础
要分析的问题
运行时间的计算

算法的定义

算法(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 }

View Code

运行时间为O（N³），主要运行时间取决于三重循环。

解法二：

 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 }

View Code

运行时间为O（N²），对第一这种方法进行了改进。

解法三：

 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 }

View Code

运行时间为O（N*logN），该方法采用了分治的设计思想，运用递归进行实现。除了小输入外，一定会比前两个快。

值得一提的是分析该运行时间时运用到了学校上课讲的递推的思想，那我必须说一下了：

该算法的时间可以用一个线性时间O（N）加上两个求解子序列问题的时间。即

ps:图片不清楚，这里是加号,N在递推时可以代替O（N）

令N=2^k且N为偶数，则有

首先T（N/2）=2*T（N/2²）+N/2

所以T（N）=2*[2*T（N/2²）+N/2]+N=2²*T（N/2²）+2*N

以此类推，有T（N）=2^k*T（N/2^k）+k*N

=2^k*T（1）+k*N

=N*1+k*N

又k=log2N，所以，T（N）=N+N*log2N，所以该算法的运行时间为O（N*logN）

在这里我们体会了如何分析算法运行时间，算法的运行时间还有其他的情况，如：

对数（二分查找、欧几里得算法）

幂（计算X^N）

学会分析一个算法的复杂度是很重要的，以后有机会我们会深入拓展。