知识卡片
性能三种情况
固定输入规模n时,最坏情况取该规模合法输入中最大的成本,最好情况取最小成本,平均情况则按明确输入概率分布计算期望。它们回答上界风险、可能的最小工作和特定工作负载下的平均成本,不能相互替代。
03141–03142对比随机、有序和近有序数据,说明同一排序方法的相对表现随输入结构变化;单一图表不能证明所有规模和环境中的排名。实际选择还要考虑尾部延迟、资源与可靠性,而平均值本身并不描述尾部。
27定义Twc(n)=max_{s∈S_n}t(s),其中S_n为规模n的合法输入集合。最坏输入的构造可以帮助分析,但仅测一个看似困难的样本不能证明它是全部输入的最大值;最坏界也不是对所有实际请求都发生的时间预测。
29说明顺序查找若第一个元素命中可提前结束;若责任是计数所有匹配项,则必须读取完整列表,其最好与最坏扫描次数均随n线性增长。若只需存在性,提前退出通常可减少部分输入的工作;不能因此否定需要完整计数的任务。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 3 处
- · 查看原书依据
三种情况进行分析: 最坏情况 定义一类输入,在这类输入下,算法表现出了最坏的运行性能。算法设计人员需要明白,这类输入的共同性质阻止了算法高效地运行,而不只是针对特定的输入。 平均情况 平均情况是表示算法在随机给定的数据上期望的执行情况。通俗地说,一些输入可能会在某些特殊情况下耗费程序大量的时间,但是
- · 查看原书依据
最长运行时间。 我们也看到,最坏情况是对整个世界的一个悲观的分析。但是我们还是非常关注最坏情况,因为: 追根刨底的欲望 这通常是对一个算法复杂度的最早的分析。 实际运行时的限制 如果你需要设计一个系统,协助外科医生进行体外循环心脏手术,那么长时间的运行(即使这种情况是不经常发生)当然不可能接受。 更
- · 查看原书依据
计数搜索(Counting Search),在n个元素中搜索v,并且记录v在表中出现的次数。如果v的计数是0,那么这个值是不存在的,所以会返回false,否则返回true。注意,计数搜索总是会搜索整个表,因此,它的最坏情况是O(n)(和顺序搜索一样),最好情况还是O(n),所以我们不能够使用这个算法