为什么 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的立方根.

一般来说，O(2^{log n}) 对于未指定的对数底数是等于 O(n^k) 对于某些 k（即多项式时间）。

Answer 2

2 ^ log2(n) = n 表示 log2，也就是 log(n) 表示性能特征（大 O）的意思。

它是 O(n)，因此是多项式（n 是多项式），而不是指数（2^n 将是指数）。