知识卡片

普通读书笔记卡 · 3588

随机算法主动引入随机性

理解等级:中级

随机算法把随机数纳入计算步骤,使相同输入也可能走出不同执行路径。

它能打散特定坏输入对确定性策略的持续打击,也可能用可控错误率换取效率;评价时须区分运行时间随机与答案可能出错。

这张卡片看不懂?

已有反馈 · 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.