知识卡片
输入情形与渐近记号分开
同样长度的数据可能让算法执行不同数量的工作。最好情形取同规模输入中的最少成本,最坏情形取最多成本,平均情形则需要先规定输入的概率分布。
大O是上界、Ω是下界、Θ是紧界,它们并不分别专属于最坏、最好和平均。原书把三者一一对应是不严谨的:任何一种情形的成本函数都可再讨论这些界。均匀位置查找的期望比较次数为(n+1)/2,增长为线性。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
算法的时间效率往往不是固定的,而是与输入数据的分布有关。假设输入一个长度为 的数组nums ,其中 nums 由从 至 的数字组成,每个数字只出现一次;但元素顺序是随机打乱的,任务目标是返回元素 的 索引。我们可以得出以
参考来源
- 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[31268,31378))
- 结论依据:findOne/打乱排列/最好最坏平均段实际支持输入情形,校正记号误配和n/2精确值。
- 原始内容:算法的时间效率往往不是固定的,而是与输入数据的分布有关。假设输入一个长度为 的数组nums ,其中 nums 由从 至 的数字组成,每个数字只出现一次;但元素顺序是随机打乱的,任务目标是返回元素 的 索引。我们可以得出以