time-complexity - 这个时间复杂度如何降低？

Question

假设我有两个因子 N 和 M，以及一个约束 M <= N，并且我有一个时间复杂度为 O(log(N)) 的操作，需要运行 M 次，但是，N 减少 1每次迭代，所以它看起来大致是这样的:

O(log(N) + log(N - 1) + ... + log(N - (M - 2)) + log(N - (M - 1)))

如何将其简化为简单的表达式？

作为奖励，我在上面简化了一些事情，N 在每次迭代时肯定不会减少 1，这只发生在最坏的情况下(其中 M = N)，它实际上减少了先前 log(N) 的结果操作，这是一些 M 数字系列，我们称之为系列 R，系列 R 和 N，所以它真的像:

O(log(N) + log(N - R(0)) + log(N - R(0) - R(1)) + ... + log(N - R(0) - R(1) - ... - R(M - 2)) + log(N - R(0) - R(1) - ... - R(M - 2) - R(M - 1)))

它是带有子求和的求和......这可以简化吗？

Answer 1

自 log(a) + log(b) = log(a*b)因此，您的等式等于:

O( log( N*(N-1)*(N-2)* ... * (N-(M-1)) * (N-M) ) )

所以对于最坏的情况 M=N-1给出上限 O(log(N!))
在一般情况下，复杂度为 O(log(N!/(N-M)!)) .正如预期的那样随着 M 增加。