V-список
Материал из Википедии — свободной энциклопедии
V-список — структура данных, разработанная Филом Багвеллом в 2002 году. V-список обьединяет в себе быстрый доступ к случайным элементам и быстрое расширение списка. V-список требует только log n дополнительной памяти, где n - количество элементов в списке. V-список состоит из обычного списка массивов, размеры которых образуют геометрическую прогрессию. Для того, чтобы найти элемент в V-списке, надо знать всего лишь адрес массива, в котором находится искомый элемент и его индекс в этом массиве. В среднем поиск случайного элемента занимает O(1) операций и O(log n) - наихудший случай.
 |
У этой статьи нет ссылок на другие языковые разделы. Вы можете помочь проекту, найдя и добавив их в статью. |
