时间戳

首页 > 解决方案 > 计算对数的复杂度

algorithm - 计算对数的复杂度

问题描述

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

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

关于如何解决这个问题并获得 Big-O 的任何想法/建议？

标签： algorithmtime-complexitycomplexity-theorylogarithm

解决方案

假设 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

推荐阅读