time - 在 O(log n) 的 log 下省略了哪个数字？

Question

在 O(log n) 中，省略了哪个底数“2”或“10”？log n 的时间复杂度是基于一个序列的划分，所以它应该是 2。通常在 log 中省略以 10 为底。

Answer 1

这种表示法显示了算法的运行时间如何随着 N 的大小而增长。它所指的基础没有区别。就像它的 O(n) 或 O(k*n) （是 ka 实常数）没有区别。

澄清：

任何给定基数 X 中的日志都可以写成如下：

log _x (n)= ^{log ₁₀ (n)} ⁄ _{log 10 (x)}

令 k=log ₁₀ (x)，所以我们有：

log _x (n)= (1 ⁄ k) × log ₁₀ (n)

这也是复杂度 log(n) 的函数

我更容易可视化这个属性的建议是认为将一个函数乘以一个常数会使它的图形垂直拉伸（或收缩），这不会改变曲线本身的形状。形状就是这个符号的含义。

来自维基百科：

同样，具有不同常数基的对数是等价的。