5

I implemented in Red-Black trees in Python according to the pseudo code in Cormen's Introduction to Algorithms.

I wanted to see in my own eyes that my insert is really O(logn) so I plotted the time it takes to insert n=1, 10, 20, ..., 5000 nodes into the tree.

This is the result:

enter image description here

the x-axis is n and the y-axis is the time it took in milliseconds.

To me the graph looks more linear than logarithmic. What can explain that?

4

3 回答 3

4

好的，所以图表显示了将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

我们可以查看 Wikipedia 以查看外观图表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 在评论中指出，如果你 plot f(n)/n，你会看到一个日志图。那是因为对 is 的一个相当严格的近似log(n!)（n*log(n)参见 Wikipedia 页面）。所以我们可以回到我们的界限：

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

并得到：

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

现在应该更容易看出，如果除以f(n)，n您的图形将在上方以对数的形状为界。

于 2012-03-02T07:48:22.150 回答
3

5000可能不够大，无法真正“看到”对数——尝试在50000and处运行500000。如果需要两秒二十秒，那么线性增长是有意义的。如果它需要更少，那么对数是有意义的。如果您在大多数“简单”函数上足够近地放大，结果看起来非常线性。

于 2012-03-01T23:31:58.327 回答
2

对于任何“为什么”的问题，总会有一些猜测。我怀疑您看到的跳跃与系统内存管理有关。如果系统必须为持续增长分配更大的内存空间，它会增加给定的时间来完成整个程序的处理。如果您向节点添加了“有效负载”字段，从而增加了所需的存储空间量，我是对的，跳转会更频繁地发生。

顺便说一句，漂亮的图表。

于 2012-03-01T23:37:06.070 回答