好的,所以图表显示了将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
您的图形将在上方以对数的形状为界。