是函数floor(log n)！ O(n)、Ω(n) 或 Θ(n)？
Is the function floor(log n)! O(n), Ω(n), or Θ(n)?
我很困惑如何计算 (log n) 的底数！
你可以忽略floor；因为 x-1 < floor(x) <= x 对于所有 x，你可以很容易地证明如果 g(x) = floor(f(x))，那么 g = Θ(f).
使用Stirling's approximation，你可以说(log n)!是Θ((log n)^(log n))，这简化为Θ(n^(log log n))，显然是Ω(n)。
（感谢 Mark Dickinson 纠正了我糟糕的数学；请参阅 here 以获得证明）。
我很困惑如何计算 (log n) 的底数！
你可以忽略floor；因为 x-1 < floor(x) <= x 对于所有 x，你可以很容易地证明如果 g(x) = floor(f(x))，那么 g = Θ(f).
使用Stirling's approximation，你可以说(log n)!是Θ((log n)^(log n))，这简化为Θ(n^(log log n))，显然是Ω(n)。
（感谢 Mark Dickinson 纠正了我糟糕的数学；请参阅 here 以获得证明）。