绘制(Cormen)红黑树插入时的奇怪结果

Question

我根据Cormen的伪代码用Python中的Red-Black树实现Introduction to Algorithms.

我想在我自己的眼睛看到我insert是真的O(logn),所以我绘制它需要插入的时间n=1, 10, 20, ..., 5000节点到树.

这是结果:

该x轴是n与y轴是它率先在时间毫秒.

对我来说,图形看起来比对数更线性.有什么可以解释的？

Answer 1

好的，该图显示了向树中插入元素的成本度量n，其中 x 轴是我们插入的元素数量，y 轴是总时间。

让我们调用一个函数来计算向树中插入 n 个元素所需的总时间f(n)。

然后我们可以大致了解一下f可能是什么样子：

f(1) < k*log(1)                 for some constant k.

f(2) < k*log(1) + k*log(2)      for some constant k

...

f(n) < k * [log(1) + log(2) + ... + log(n)]   for some constant k.

由于日志的工作方式，我们可以崩溃log(1) + ... + log(n)：

f(n) < k * [log(1*2*3*...*n)]     for some constant k

f(n) < k * log(n!)                for some constant k

我们可以看一下维基百科，看看是什么样的图表log(n!)。看看文章中的图表。你应该看起来很熟悉。:)

也就是说，我认为你这样做是偶然的：

for n in (5000, 50000, 500000):
    startTime = ...
    ## .. make a fresh tree
    ## insert n elements into the tree
    stopTime = ...
    ## record the tuple (n, stopTime - startTime) for plotting

并绘制了构建大小为 n 的树的总时间，而不是向大小为 n 的树中插入一个元素的单独成本：

for n in range(50000):
    startTime = ...
    ## insert an element into the tree
    stopTime = ...
    ## record the tuple (n, stopTime - startTime) for plotting

Chris Taylor 在评论中指出，如果绘制f(n)/n，您将看到一个对数图。log(n!)这是因为对is的相当严格的近似n*log(n)（参见维基百科页面）。所以我们可以回到我们的界限：

f(n) < k * log(n!)                for some constant k

并得到：

f(n) < k * n * log(n)             for some constant k

现在应该更容易看出，如果除以f(n)，n您的图形将受到对数形状的限制。