Geek asks and answers

Input coding (time complexity)

Not sure if this is the right place to ask about this. In Cormen, p. 1056, I read that if the running time of the O (k) and "k" algorithm is represented in unary, i.e. A string is from k 1s, then the execution time of the algorithm is 0 (n), where "n" is the size of the input bit in bits and if "k" is represented as binary, whereas n = log k + 1, the running time of the algorithm becomes o (2 ^ n).

So, therefore, I doubt why a “unary” representation would not be preferable in this case, since it gives polynomial time as opposed to exponential in another case.

+3
source share
1 answer

, .

, . , .
k n, O(k) - O(n) - . O(k) = O(2^logk) = O(2^n), , logk bits k.

, , , knapsack , O(W*n), , W.

+4

More articles:


All Articles