知识卡片
复杂度输入规模取编码长度
计算机处理的是抽象实例的二进制编码;复杂度分析中的输入规模是编码串长度|i|,不是对象的直观数量。
不同编码会影响长度,因此称某问题属于P时,需明确具体问题及合理编码。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Thus, a computer algorithm that “solves” some abstract decision problem actually takes an encoding of a problem instance as input. The size of an instance i is just the length of its string, which we denote by |i|. We call a problem whose instance set is the set of binary strings a concrete problem. We say that an algorithm solves a concrete problem in O(T (n)) time if, when it is provided a problem instance i of length n = |i|, the algorithm can produce the solution in O(T (n)) time.
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[15000,20000))。
- 结论依据:原文复杂度类别、判定问题、归约或编码定义;不把P与NP的未解关系写成已证明结论。
- 原始内容:Thus, a computer algorithm that “solves” some abstract decision problem actually takes an encoding of a problem instance as input. The size of an instance i is just the length of its string, which we denote by | i |. We call a problem whose instance set is the set of binary strings a concrete problem . We say that an algorithm solves a concrete problem in O ( T ( n )) time if, when it is provided a problem instance i of length n = | i |, the algorithm can produce the solution in O ( T ( n )) time.