为什么log（）“O（log（n））”的Big-O而不是“O（n）”？

Question

互联网有很多资源解释了对于日志因子函数的Big-O（例如1，2），它是O(n log(n))。

我不明白为什么log()有O(log(n))而不是至少O(n)。从下面的递归代码，log_factorial基本上被称为n次（这意味着log()被称为n次），所以如果log()是O(n)，log_factorial应该是O(n^2)。

log_factorial <- function (n) {
  # Return the log of factorial(n) for any integer n > 0
  if (n <= 1)
    return (0)
  return ( log(n) + log_factorial( n - 1 ) )
}

查看互联网对我没什么帮助（相反，它让我更加困惑）。 Wikipedia说log的Big-O应该取决于精度：

...计算自然对数（使用算术几何平均值）是O（M（n）ln n）。这里n是要评估自然对数的精度的位数，M（n）是乘以两个n位数的计算复杂度。

为了获得经验答案，我绘制了运行时间与n（下图）的关系，实际上，对数因子不是二次的。

我显然在这里遗漏了一些东西，希望有人可以向我解释。如果我的问题是'noob-ish'，请原谅我。

Answer 1

TL; DR：没有办法告诉Big-O log（n），只能告诉log（n）的特定实现。

您试图推断出您未完全指定的算法的Big-O。没有人知道你（或各种互联网资源）对于对数函数的实现。

我非常确定每个半正常的log（n）实现将比O（n）执行得更好：log（1000000）不会比log（1000）长1000倍。

在评论中，给出了在O（logn）中执行log（n）的合理方法，我认为甚至可以有更好的方法。

对于数千范围内的值（如图中所示），我甚至可以为您提供一个O（1）解决方案，其中包含一个预先计算的日志值表。