为什么O(2 ^ log(n))= O(n)并且它不是指数运行时间？

Question

为什么O(2^log(n))相当于O(n)？另外为什么这被认为是指数运行时而不是多项式运行时？

Answer 1

此语句有时是真的,有时也是假的,具体取决于对数的基数.例子:

• O(2 ^{lg n})= O(n),其中lg是二进制对数.

• O(2 ^{log_4 n})= O(n ^1/2),其中log_4是基数4的对数.

• O(2 ^{log_1.25992 n})= O(n ³),因为1.25992是2的立方根.

通常,对于某些k(这是多项式时间),未指定对数基数的O(2 ^{log n})等于O(n ^k).