知识卡片
正确性覆盖全部实例
正确性要求算法对每个合法问题实例都在有限时间内终止并给出符合问题定义的答案。
只在常见样例上成功不足以证明正确;若允许概率错误,必须另行声明错误率及其控制条件。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第1章 算法在计算中的作用 · 查看原书依据
An algorithm for a computational problem is correct if, for every problem instance provided as input, it halts—finishes its computing in finite time—and outputs the correct solution to the problem instance. A correct algorithm solves the given computational problem.
参考来源
- 位置:《算法导论(第4版)》第 1 章《算法在计算中的作用》(源文件:`OEBPS/chapter001.xhtml`)
- 结论依据:第1章正确性定义要求每个输入实例都终止并给出正确解;样例成功不是全称保证。概率错误需另行声明,是对严格正确定义的边界说明。
- 原始内容:An algorithm for a computational problem is correct if, for every problem instance provided as input, it halts —finishes its computing in finite time—and outputs the correct solution to the problem instance. A correct algorithm solves the given computational problem.