74
Глава 5. Двусвязный список
чтобы получить хороший диапазон данных. В измерениях
присутствовало больше неточностей, чем в предыдущей группе;
вот результаты:
128000, 16
256000, 19
512000, 28
1024000, 77
2048000, 330
4096000, 892
8192000, 1047
16384000, 4755
На рис. 5.2 показан график результатов.
Это не очень прямая линия, и тангенс угла наклона точно
не равен 1; тангенс угла наклона аппроксимирующей пря-
мой, полученной методом наименьших квадратов, равен 1,23.
Но данный результат показывает, что полное время выполне-
ния n добавлений по крайней мере приблизительно составля-
ет O(n), таким образом, каждое добавление выполняется за
постоянное время.
Добавление в конец
LinkedList
Добавление элементов в начало — одна из операций, для ко-
торых мы ожидаем, ...