<分区>
我有一个算法，其运行时间与 log(1) + log(2) + ... + log(N) 成正比。显然，该算法在 O(N log(N)) 时间内运行。然而，我有一种直觉，可能会有更严格的界限，因为我生成的那个使用最大对数项的值来限制所有对数项，即使许多项要小得多。我对么？是否有更严格的界限，仍然可以简单地用算术表达？
<分区>
我有一个算法，其运行时间与 log(1) + log(2) + ... + log(N) 成正比。显然，该算法在 O(N log(N)) 时间内运行。然而，我有一种直觉，可能会有更严格的界限，因为我生成的那个使用最大对数项的值来限制所有对数项，即使许多项要小得多。我对么？是否有更严格的界限，仍然可以简单地用算术表达？
最佳答案
log(1) + log(2) + ... + log(N) 将是 log(1*2*3*4*5*..... ..*n)
等于 log (n!)
斯特林近似
Sterling's Approximation
可以等同于 log(n^n) 因为 log (a^b)= b log a
相当于(n log n)
并回答你的另一个问题，在这种情况下我看不出有任何更严格的限制。
我希望这会有所帮助。
关于algorithm - 运行时间与日志总和成正比的算法的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45529317/
