知识卡片

普通读书笔记卡 · 1708.b.3.a · 生成模型:未记录

性能三种情况

理解等级:中级

固定输入规模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),所以我们不能够使用这个算法

    参考来源

    《算法技术手册》第02章《算法的数学原理》 - 位置:《算法技术手册》第2章《最好最坏和平均情况下的性能分析》(spine1463;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1427.html;u026-ch02-002)。 - 结论依据:26全文及03141–03142全部图表实读;保留原卡路径并补充条件。 - 原始内容:三种情况进行分析: 最坏情况 定义一类输入,在这类输入下,算法表现出了最坏的运行性能。算法设计人员需要明白,这类输入的共同性质阻止了算法高效地运行,而不只是针对特定的输入。 平均情况 平均情况是表示算法在随机给定的数据上期望的执行情况。通俗地说,一些输入可能会在某些特殊情况下耗费程序大量的时间,但是 - 位置:《算法技术手册》第2章《最坏情况》(spine1463;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1427.html;u027-ch02-002)。 - 结论依据:27定义Twc(n)=max_{s∈S_n}t(s),其中S_n为规模n的合法输入集合。最坏输入的构造可以帮助分析,但仅测一个看似困难的样本不能证明它是全部输入的最大值;最坏界也不是对所有实际请求都发生的时间预测。 - 原始内容:最长运行时间。 我们也看到,最坏情况是对整个世界的一个悲观的分析。但是我们还是非常关注最坏情况,因为: 追根刨底的欲望 这通常是对一个算法复杂度的最早的分析。 实际运行时的限制 如果你需要设计一个系统,协助外科医生进行体外循环心脏手术,那么长时间的运行(即使这种情况是不经常发生)当然不可能接受。 更 - 位置:《算法技术手册》第2章《最好情况》(spine1465;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1429.html;u029-ch02-002)。 - 结论依据:29说明顺序查找若第一个元素命中可提前结束;若责任是计数所有匹配项,则必须读取完整列表,其最好与最坏扫描次数均随n线性增长。若只需存在性,提前退出通常可减少部分输入的工作;不能因此否定需要完整计数的任务。 - 原始内容:计数搜索(Counting Search),在n个元素中搜索v,并且记录v在表中出现的次数。如果v的计数是0,那么这个值是不存在的,所以会返回false,否则返回true。注意,计数搜索总是会搜索整个表,因此,它的最坏情况是O(n)(和顺序搜索一样),最好情况还是O(n),所以我们不能够使用这个算法