Хорошо, поэтому график отображает измерение стоимости вставки 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
Крис Тейлор отмечает в комментариях, что если вы построите график 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, ваш график будет ограничен сверху формой логарифма.