time-complexity - 每一步进行 O(log n) 操作时的总时间复杂度

Question

考虑一棵插入成本为 的树O(log n)。假设您从一棵空树开始并迭代添加 N 个元素。我们想知道总时间复杂度。我这样做了：

nb of operations in iteration i = log i
nb of operations in all iterations from 1 to N = log 1 + log 2 + ... + log N = log( N! ) 
total complexity =  O(N!) ~ O(N log N)

（参见斯特林近似http://en.wikipedia.org/wiki/Stirling%27s_approximation）

这个对吗？

Answer 1

是的，它几乎是正确的。

一个小修正：在第ith 步中，操作数不是 log i，因为大多数时候这是一个无理数，它是O(log i)。因此，对于数学上严格的证明，您必须更加努力，但简而言之，您所写的是证明的本质。