计算对数的复杂度

Question

众所周知，将节点插入 AVL 树的复杂度为 log(c)，而 c 是树内的节点数。我希望将 m 个节点插入树中，因此复杂度为：

log(c)+log(c+1)+...+log(c+m)

关于我如何解决这个问题并获得 Big-O 的任何 ideas/suggestions？

Answer 1

假设 c 不是常数：

log(c)+log(c+1)+...+log(c+m) = log(c * (c+1) * .... * (c+m))
                     = log((m+c)!/c!)
                     = log((m+c)!) - log(c!)
                     = O_theta((m+c)log(m+c)- clogc)

但是为了 Big-O 的复杂性，我们通常引用松散边界：O(NlogN) 其中 N=m+c

计算对数的复杂度

Calculating complexity of logarithm

algorithm

time-complexity

complexity-theory

logarithm