Хобрук: Ваш путь к мастерству в программировании

Время вставки и удаления в списке пропуска

Меня немного смущает время, необходимое для вставки или удаления элемента из списка пропуска.

Допустим, есть список пропуска высотой H, и каждый уровень содержит n/2^i записей.
n = общее количество пар ключ-значение
i = уровень списка пропуска i‹= H

Теперь согласно теории операция вставки будет выполнять следующие действия
1. Найти ключ ‹= вставляемому ключу.
2. вставить этот ключ
3. случайным образом создать эту запись в выше базового уровня.

Предположим, что список пропуска основан на связанном списке.
Шаг 1: Должен занять O(n).
Шаг 2: Должен быть O(1).
Шаг 3: Должен быть O(log n) времени. Я все еще запутался в этой логике, и это будет частью вопроса ниже

Вопрос

  1. Основываясь на приведенных выше фактах, не должно ли время вставки быть O (n) + O (1) + O (log n)? игнорируя условия более низкого порядка, он должен идти O (n) + O (log n)?

  2. Шаг 3 снова должен занять O(n) времени для поиска ключа ‹= вставляемого ключа, а затем o(1) для вставки. Что приводит к очень сложному времени выполнения вставки?

В книгах говорится, что вставка в список пропуска занимает время O(log n). Должно быть, мне не хватает какой-то важной информации, не могли бы вы помочь мне понять эту концепцию.

algorithm insertion skip-lists
01.09.2012

Ответы:


1

Весь смысл списка пропуска заключается в том, что не нужно просматривать весь список, чтобы найти элемент. Сначала вы ищете в верхнем списке, затем спускаетесь на один уровень вниз и так далее, пока не дойдете до базового списка.

Допустим, верхний список содержит 2 элемента, первый и один где-то посередине. Когда вы ищете свой предмет, список уже сокращается вдвое. Каждый уровень будет сокращать список примерно вдвое. Это то, что делает вставку O (log n).

01.09.2012
  • Просто для подтверждения. Это означает, что мы не можем реализовать список пропусков с использованием любого другого вектора для выступлений того же времени? Потому что, если бы это был двумерный массив, я бы никогда не получил индекс позиций вставки с более высоких уровней, не просматривая каждый элемент. 02.09.2012
  • Я не совсем понимаю ваш вопрос, но списки пропуска реализуются со связанными списками. 02.09.2012

    • 2

    Поскольку списки пропуска используются для хранения отсортированных данных, вы можете сделать что-то более разумное, чем линейный поиск, при поиске позиции для вставки нового элемента.

    По сути, вы можете сделать что-то похожее на бинарный поиск, используя указатели на более высоких уровнях. Например, проверив ссылку на уровне log n - 1, вы можете сравнить новый элемент с элементом в середине списка, тем самым определив, должен ли он быть вставлен в первую или во вторую половину списка. Затем вы продолжаете в том же духе, каждый раз просматривая ссылки на более низких уровнях, чтобы повысить точность. Это снижает сложность шага 1 в вашем алгоритме до O(log n).

    01.09.2012
    Новые материалы
    Создание кнопочного меню с использованием HTML, CSS и JavaScript
    Вы будете создавать кнопочное меню, которое имеет состояние наведения, а также позволяет вам выбирать кнопку при нажатии на нее. Финальный проект можно увидеть в этом Codepen . Шаг 1..
    Внедрите OAuth в свои веб-приложения для повышения безопасности
    OAuth — это широко распространенный стандарт авторизации, который позволяет приложениям получать доступ к ресурсам от имени пользователя, не раскрывая его пароль. Это позволяет пользователям..
    Классы в JavaScript
    class является образцом java Script Object. Конструкция «class» позволяет определять классы на основе прототипов с чистым, красивым синтаксисом. // define class Human class Human {..
    Как свинг-трейдеры могут использовать ИИ для больших выигрышей
    По мере того как все больше и больше профессиональных трейдеров и активных розничных трейдеров узнают о возможностях, которые предоставляет искусственный интеллект и машинное обучение для улучшения..
    Как построить любой стол
    Я разработчик программного обеспечения. Я люблю делать вещи и всегда любил. Для меня программирование всегда было способом создавать вещи, используя только компьютер и мое воображение...
    Обзор: Машинное обучение: классификация
    Только что закончил третий курс курса 4 часть специализации по машинному обучению . Как и второй курс, он был посвящен низкоуровневой работе алгоритмов машинного обучения. Что касается..
    Разработка расширений Qlik Sense с qExt
    Использование современных инструментов веб-разработки для разработки крутых расширений Вы когда-нибудь хотели кнопку для установки переменной в приложении Qlik Sense? Когда-нибудь просили..