文档介绍：第2章算法分析基础
学****要点:
掌握算法分析中的算法复杂度概念
时间复杂度、空间复杂度
最好、最坏和平均情况时间复杂度
掌握算法分析的渐近表示法
掌握用C++语言描述算法的方法
章节内容:
算法复杂度
渐近表示法
递推关系(课外阅读)
算法复杂度
好算法的4个重要特征:
Correctness——正确性
注意区分“正确性”和“健壮性”的概念:
算法正确性——在合法的输入下,算法应实现预先规定的功能和计算精度要求。
程序健壮性——当输入不合法的数据时,程序应能做适当处理而不至于引起严重后果。
正确性和健壮性互相补充。
程序可靠性——在正常情况下能正确地工作,在异常情况下也能做出适当处理。
算法复杂度
好算法的4个重要特征:
Correctness——正确性
Simplicity, clarity——简明性
遗憾的是,简单的算法不一定高效
思路清晰、层次分明、容易理解、利于编码和调试。
算法复杂度
好算法的4个重要特征:
Correctness——正确性
Simplicity, clarity——简明性
Amount of time/space used——效率
执行算法所需的时间和存储空间
算法设计者常常需要在算法的简明性和效率之间作出谨慎的选择
算法复杂度
好算法的4个重要特征:
Correctness——正确性
Simplicity, clarity——简明性
Amount of time/space used——效率
Optimality——最优性
算法执行时间达到求解该类问题所需时间的下界。
与所求解问题自身的复杂程度有关。
For problem P, the algorithm A does at most WA(n) steps in the worst case (upper bound)
F is a lower bound for a class of algorithm. (lower bound)
If WA=F, then A is optimal.
Definition of the optimal algorithm(最优算法)
means that: For any algorithm in the class, and any input of size n, there is some input of size n for which the algorithm must perform at least F(n) basic operations.
又如:
可证排序问题的时间复杂度下界为(nlogn)。
则最坏时间复杂性为O(nlogn)的排序算法是最优算法。因此:堆排序算法和两路合并排序算法都是最优算法。
例如:FindMax(int L[]) //求n个元素中的最大元素
{
int max=L[0]; int i=1;
while(i<n)
{
if (max<L[i]) max=L[i];
i=i+1;
}
}
最优算法
影响程序运行时间的因素
程序所依赖的算法
问题规模和输入数据
计算机系统性能
根本的、起决定作用的
数值大小和状态
硬件系统性能(CPU速度)和软件系统性能(操作系统、编译器)
输入、输出
——运行一个算法所需的时间和空间资源的量。
算法的时间复杂性(plexity)——T(n)
算法的空间复杂性(plexity)——S(n)
其中n是问题的规模(输入大小)
算法复杂度
How to Measure?
Machine independent
Language independent
Programming style independent
Implementation independent