知识卡片
性能情况由输入条件决定
同一算法在相同规模下,也可能因输入内容和位置不同执行不同数量的操作。线性查找首项命中只需检查一项,末项命中或不存在则可能扫描全体;这分别形成不同的分析情况。
平均情况需要说明输入或命中位置的分布,不能仅把“中间位置”叫作普遍平均。先选定规模、允许的输入和计量方式,再比较最佳、最坏或分布下的期望,避免把一次运行代表所有情况。
41以不存在元素和搜索首项比较说明最坏分析的用途。上界只针对所选输入范围和成本模型,不包硬件故障、无限数据或未计成本;原文“其他情况肯定更好”应改为不更差,可能相等。最佳情况也并非永远无用,是否有信息取决于任务。
170排序应用中的“相同复杂度/常量差”须限定分析情形:堆排序常用最坏O(n log n),快速排序常见期望/平均O(n log n),并非二者所有情况都相同;快排最坏可平方,具体算法留第12章。不能把常数差称为另一种复杂度等级。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 3 处
- · 查看原书依据
最佳情况、平均情况与最坏情况。对于任何算法来说,理解每种情况是如何产生的对于分析算法来说非常重要,因为算法在不同的情况下性能差异可能很大。看一种线性搜索的简单算法。线性搜索是一种自然的但效率低下的搜索技术,它简单地从数据集的头部顺序遍历到尾部。在最佳情况下,要查找的元素处于数据集的第一个位置,所以在
- · 查看原书依据
最坏情况可以告诉我们算法性能的上限。分析一个算法的最坏情况可以保证在任何情况下此算法的表现都不会比最坏情况差,而其他情况肯定比最坏情况要好。 虽然我们把最坏情况当做很多算法性能的度量,但也有例外。因为有些时候我们也会用平均情况来评判算法性能。例如:随机算法中的快速排序算法(见第12章),它使用了概率
- · 查看原书依据
堆排序与快速排序(见第12章)有相同的时间复杂度,但是在实际中,快速排序往往比堆排序复杂度略低,两者相差一个常量因子。 任务调度 任务调度会告诉操作系统接下来哪个进程将在CPU上运行。操作系统会不断调整进程的优先级。用优先队列来存储进程是相对比较高效的方法,因为它可以确保下一个将在CPU中运行的进程