algorithm - 表达式的渐近运行时间复杂度

Question

我可以这样说吗:

log n + log (n-1) + log (n-2) + .... + log (n - k) = theta(k * log n)?

上面的正式写法:

Sigma(i 从 0 到 k)log (n-i) = theta (k* log n)?

如果上面的说法是正确的，我该如何证明呢？

如果它是错误的，我如何将它(当然是等式的左边)表示为 n 和 k 的渐近运行时间函数？

谢谢。

Answer 1

表示:

LHS = log(n) + log(n-1) + ... + log(n-k)

RHS = k * log n

注意:

LHS = log(n*(n-1)*...*(n-k)) = log(第 (k+1) 阶多项式)

因此这等于:

(k+1)*log(n(1 + 极限为 0 的项))

如果我们考虑除法:

(k+1)*log(n(1 + 极限为 0 的项))/RHS

我们进入极限:

(k+1)/k = 1 + 1/k

因此，如果 k 是常数，则两项增长速度相同。所以 LHS = theta(RHS)。

Wolfram Alpha seems to agree.

当 n 为常量时，之前限制为 0 的项不会消失，而是您会得到:

(k+1) * 一些常量/k *(其他一些常量)

是这样的:

(1 + 1/k)*(另一个常数)。 LHS = theta(RHS)也是如此。