输入编码(时间复杂度)

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.

你所描述的与伪多项式时间算法密切相关,例如带有动态编程的背包解决方案O(W*n),它是伪多项式,因为它实际上是用于表示的位数的指数W.