知识卡片

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

一元编码会改变多项式判断

理解等级:中级
  • 同一算法若耗时Θ(k),输入k用一元编码时长度为k,耗时对输入长度是线性的;
  • 用二进制时长度约为log k,耗时对输入长度可呈指数增长。

谈抽象问题复杂度前须固定合理编码。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      For example, suppose that the sole input to an algorithm is an integer k, and suppose that the running time of the algorithm is Θ(k). If the integer k is provided in unary—a string of k 1s—then the running time of the algorithm is O(n) on length-n inputs, which is polynomial time. If the input k is provided using the more natural binary representation, however, then the input length is n = ⌊lg k⌋ + 1, so the size of the unary encoding is exponential in the size of the binary encoding. With the binary representation, the running time of the algorithm is Θ(k) = Θ(2n), which is exponential in the size of the input. Thus, depending on the encoding, the algorithm runs in either polynomial or superpolynomial time. The encoding of an abstract problem matters quite a bit to how we understand polynomial time. We cannot really talk about solving an abstract problem without first

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[20000,25000))。 - 结论依据:原文§34.1–34.2的编码、形式语言、验证定义及证明;章末练习不作已解结论。 - 原始内容:For example, suppose that the sole input to an algorithm is an integer k , and suppose that the running time of the algorithm is Θ( k ). If the integer k is provided in unary —a string of k 1s—then the running time of the algorithm is O ( n ) on length- n inputs, which is polynomial time. If the input k is provided using the more natural binary representation, however, then the input length is n = ⌊ lg k ⌋ + 1, so the size of the unary encoding is exponential in the size of the binary encoding. With the binary representation, the running time of the algorithm is Θ( k ) = Θ(2 n ), which is exponential in the size of the input. Thus, depending on the encoding, the algorithm runs in either polynomial or superpolynomial time. The encoding of an abstract problem matters quite a bit to how we understand polynomial time. We cannot really talk about solving an abstract problem without first