Список с пропусками
Материал из Википедии — свободной энциклопедии
Список с пропусками - разновидность упорядоченного списка, позволяющий быстро находить любой его элемент. В обычном упорядоченном списке для поиска необходимо просматривать все элементы по порядку, таким образом поиск произвольного элемента занимает в среднем n/2 операций, где n - количество элементов в списке. Список с пропусками содержит специальные дополнительные указатели, позволяющие "перескочить" через определённое количество элементов, таким образом можно реализовать более быстрый поиск, занимая всего O(log1/p n / p) операций, где p - константа.
|
Для улучшения статьи желательно:
|
