Я реализовал красно-черные деревья на Python в соответствии с псевдокодом в Introduction to Algorithms Кормена.
Я хотел своими глазами увидеть, что мой insert на самом деле O(logn), поэтому я наметил время, необходимое для вставки n=1, 10, 20, ..., 5000 узлов в дерево.
Вот результат:
ось x — это n, а ось y — это время в миллисекундах.
Для меня график выглядит более линейным, чем логарифмическим. Чем это можно объяснить?
Итак, на графике отображается измерение стоимости вставки 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, ваш график будет ограничен сверху формой логарифма.
f(n)/n, вы увидите, что ваш логарифмический график выглядит просто как день.
- person Chris Taylor; 02.03.2012
5000 может быть недостаточно большим, чтобы действительно «увидеть» логарифм — try работает с 50000 и 500000. Если это занимает две секунды и двадцать секунд, то линейный рост имеет смысл. Если требуется меньше, то логарифмический имеет смысл. Если вы достаточно приблизите большинство «простых» функций, результаты будут выглядеть довольно линейно.
50000 занимает 2,5 секунды, а 500000 занимает ~ 30, что, согласно вашей гипотезе, выглядит линейным.
- person Zack; 02.03.2012
На любой вопрос «почему» всегда есть несколько предположений. Я подозреваю, что скачки, которые вы видите, связаны с управлением системной памятью. Если системе необходимо выделить больший объем памяти для дальнейшего роста, это добавит заданное количество времени для завершения обработки всей программы. Если вы добавили поле «полезная нагрузка» к своим узлам, тем самым увеличив объем необходимого пространства для хранения, и я прав, переходы будут происходить чаще.
Хороший график, кстати.
