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

Question

我是根据Cormen的Introduction to Algorithms中的伪代码用Python实现红黑树的。

我想亲眼看看我的 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

我们可以看看维基百科，看看graph 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!) 的一个相当严格的近似是 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，您的图表将以对数形状为界。