知识卡片

普通读书笔记卡 · 3713.a.1

复杂度输入规模取编码长度

理解等级:中级

计算机处理的是抽象实例的二进制编码;复杂度分析中的输入规模是编码串长度|i|,不是对象的直观数量。

不同编码会影响长度,因此称某问题属于P时,需明确具体问题及合理编码。

这张卡片看不懂?

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