知识卡片
随机算法主动引入随机性
随机算法把随机数纳入计算步骤,使相同输入也可能走出不同执行路径。
它能打散特定坏输入对确定性策略的持续打击,也可能用可控错误率换取效率;评价时须区分运行时间随机与答案可能出错。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第一部分 基础知识 · 查看原书依据
An algorithm whose behavior is determined not only by its input but by the values produced by a random-number generator is a randomized algorithm. You can use randomized algorithms to enforce a probability distribution on the inputs—thereby ensuring that no particular input always causes poor performance—or even to bound the error rate of algorithms that are allowed to produce incorrect results on a limited basis.
参考来源
- 位置:《算法导论(第4版)》第一部分《基础知识》引言(源文件:`OEBPS/part001.xhtml`)
- 结论依据:原文分别说明概率分析依赖输入分布,以及随机算法把随机数引入算法行为并可影响性能或错误率。
- 原始内容:An algorithm whose behavior is determined not only by its input but by the values produced by a random-number generator is a randomized algorithm. You can use randomized algorithms to enforce a probability distribution on the inputs—thereby ensuring that no particular input always causes poor performance—or even to bound the error rate of algorithms that are allowed to produce incorrect results on a limited basis.