算法效率分析（原创文章）
算法是一系列解决问题的明确指令，对于一定符合规范的输入，能够在有限时间内获得要求的输出。从实际问题的提出到设计合适的算法再到正确性的分析以及算法效率的分析，最后为算法编写代码，一步步得到问题的解决方案。
图1.算法的概念
图2.算法设计分析过程
对算法效率的分析，需要指出有两种算法效率：时间效率和空间效率，分指算法运行速度和需要的额外空间。由于技术革新，对于大多数问题，速度上效率的提高远大于空间上的提高。在研究算法效率上提出一般性框架。
定义1：如果存在正常数c和
使得当
时
，则记为
。
定义2：如果存在正常数c和
使得当
时
，则记为
。
定义3：
当且仅当
且
。
定义4：如果
且
，则
。
定义的目的实在函数之间建立相对的级别。可直观的理解为
增长率小于等于
，
增长率大于等于
，
增长率等于
，
增长率小于
。
法则1：如果
且
，那么
（a）
（b）
法则2：如果
是k次多项式，则
法则3：对任意常数k，
下面以最大子序列和问题的四种解决方法来分析算法的效率问题。
最大子序列和：给定整数
（可能含负数），求
最大值（若所有整数为负，则最大子序列和为0）
| 算法 |
1 | 2 | 3 | 4 | |
| 时间 |
 |
 |
 |
 |
|
| 输入大小/m | N=10 |
0.00103 | 0.00045 |
0.00066 |
0.00034 |
| N=100 | 0.47015 |
0.01112 |
0.00486 |
0.00063 |
|
| N=1000 | 448.77 |
1.1233 |
0.05843 |
0.00333 |
|
| N=10000 | NA |
111.13 |
0.68631 |
0.03042 |
|
| N=100000 | NA |
NA |
8.0113 | 0.29832 |
方法一、穷举尝试所有可能，含有3重for循环。第一循环大小为N，第二循环大小为
，第三循环大小为
。考虑最差时间效率，第二循环第三循环大小均为N。总数为
。可精确分析，第三循环时间
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; } |
方法二、在方法一的基础上去掉三重循环，复杂度降为
int MaxSubsequenceSum(const int A[], int N) { int ThisSum, MaxSum, i, j, k; MaxSum = 0; for (i = 0; i < N; i++) { ThisSum = 0; for (j = i; j < N; j++) { ThisSum += A[k]; if (ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum; } |
方法三、使用一种递归的方法，使复杂度降为
。当问题无法找到
复杂度的线性解法前，该方法很好的体现递归的强力。方法使用“分治”策略。将问题“分割”成两个大致相等的子问题，再将两个子问题的解合并，再做少量工作使问题解决。
假设测试序列：
| 前半部 | 后半部 | ||||||
| 4 |
-3 | 5 |
-2 | -1 |
2 |
6 | -2 |
1前半部最大子序列和为6（
），后半部最大子序列和为8（
）
2前半部包含最后元素最大和为4（
），后半部第一元素最大和为7（
）
3两部分最大和11（
）
算法3比前两种需要更多代码量，但在运行时间上，特别是大数据量的运算时间，会比前两种方法节省更多时间。
方法四、极为简洁而且更加的有效。打破了第二循环和第三循环，使运行时间变为线性。
int MaxSubsequenceSum(const int A[], int N) { int ThisSum, MaxSum, j; MaxSum = ThisSum = 0; for (j = 0; j < N; j++) { ThisSum += A[j]; if (ThisSum > MaxSum) MaxSum = ThisSum; else if (ThisSum < 0) ThisSum = 0; } return MaxSum; } |
在实际的代码编写中，对算法复杂度进行估算，可以更加有计划性的进行算法改进。提高时间效率。
当前暂无评论，小编等你评论哦！
