|
|
|
|
知识路径： > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 算法设计与分析 > 算法分析基础 >
|
|
|
被考次数：1次
|
|
|
被考频率：
低频率
|
|
|
总体答错率：
65%
|
|
知识难度系数：
|
|
|
考试要求：
掌握
|
|
|
相关知识点：2个
|
|
|
|
|
算法的时间复杂度分析主要是分析算法的运行时间，即算法所执行的基本操作数。即使对相同的输入规模，数据分布不相同也决定了算法执行不同的路径，因此所需要的执行时间也不相同。根据不同的输入，将算法的时间复杂度分为3种情况。
|
|
|
|
（1）最佳情况。使算法执行时间最少的输入。一般情况下，不进行算法在最佳情况下的时间复杂度分析。应用最佳情况分析的一个例子是已经证明基于比较的排序算法的时间复杂度下限为Ω(nlgn)，那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度。
|
|
|
|
（2）最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，它提供了一个保障，情况不会比这更糟糕。另外，对于某些算法来说，最坏情况还是相当频繁的。而且大致上看，平均情况通常与最坏情况的时间复杂度一样。
|
|
|
|
（3）平均情况。算法的平均运行时间。一般来说，这种情况很难分析。举个简单的例子，现要排序10个不同的整数，输入就有10!种不同的情况，平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按以下3个步骤进行。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
式中，pi为第i类输入发生的概率；ti为第i类输入的执行时间，输入分为m类。
|
|
|
