不确定这是否是问这个问题的正确地方。在 Cormen 第 1056 页中，我读到如果算法的运行时间为 O(k)，并且“k”以一元表示，即 k 1s 的字符串，则该算法的运行时间为 0(n)，其中“n”是输入大小以位为单位，如果“k”表示为二进制，则 n=lg k+1 ，算法的运行时间变为 o(2^n)。
所以我的疑问是为什么在这种情况下不会首选“一元”表示，因为它给出了多项式时间，而在其他情况下是指数。
问问题
2655 次
1 回答
6
一元时间给出了相对于输入大小的多项式时间，但实际运行时间是相同的，无论使用何种表示。
问题是复杂性是作为输入的函数计算的。使用一元表示时，您会增加输入的大小，而不会更改运行时间。
由于要k以一元基数表示您需要n位，O(k)因此是O(n)- 因为它在输入的大小上是线性的。O(k) = O(2^logk) = O(2^n)但是，对于相同的解决方案，如果您使用二进制表示，它将是，因为您需要logk位来表示k。
您所描述的与伪多项式时间算法密切相关，例如具有动态规划的背包O(W*n)解决方案，它是伪多项式，因为它实际上是用于表示的位数的指数W。
于 2012-05-02T21:35:48.463 回答