编码的输入（时间复杂度）

Question

不知道这是否是正确的地方问这个问题。 在Cormen的第1056页我读到，如果一个算法的运行时间是O（k）并且“k”以一元表示，即一串k 1s，那么该算法的运行时间是0（n），其中“n”是输入大小为比特，如果“k”表示为二进制，则n = lg k + 1，算法的运行时间变为o（2^n）。

所以，我的疑问是，为什么在这种情况下“一元”表示不会被优先选择，因为它在多种情况下给出多项式时间，而在其他情况下则是指数。

Answer 1

一元时间给出相对于输入尺寸的多项式时间，但的实际运行时间是相同的，无论使用何种表示。

问题是复杂度是作为输入函数计算的。使用一元表示法时，可以增加输入的大小，而不会改变运行时间。
由于代表k一元的基地，你需要n位，O(k)是O(n) - 因为它是在输入的大小是线性的。但是，对于相同的解决方案，如果使用二进制表示，则它将为O(k) = O(2^logk) = O(2^n)，因为您需要logk位来表示k。

你所描述密切相关pseudo-polynomial time算法，如knapsack解决方案与动态规划算法是O(W*n)，它是伪多项式，因为它实际上是在用来表示W位的数量指数。