知识卡片
一元编码会改变多项式判断
- 同一算法若耗时Θ(k),输入k用一元编码时长度为k,耗时对输入长度是线性的;
- 用二进制时长度约为log k,耗时对输入长度可呈指数增长。
谈抽象问题复杂度前须固定合理编码。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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