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

почему временная сложность zpopmin равна log n?

из документа Redis:

Ключ ZPOPMIN [количество] Доступно с версии 5.0.0.

Временная сложность: O(log(N)*M), где N — количество элементов в отсортированном наборе, а M — количество извлеченных элементов.

Удаляет и возвращает до подсчета членов с наименьшими оценками в отсортированном наборе, хранящемся в ключе.

Итак, мой вопрос: если список отсортирован, почему он занимает log n, а почему не O (1)?

redis
26.01.2019

Ответы:


1

Если список отсортирован, почему он занимает log n, а почему не O(1)?

Если бы отсортированные наборы были реализованы со списками, вы могли бы сделать это за время O(1) для каждого элемента. Однако отсортированные наборы реализованы (частично) с Структура данных списка пропуска, которая выполняет вставки и удаления за время O(log(N)).

26.01.2019
  • Если у меня есть ссылка на начало списка, почему удаление первого элемента занимает больше, чем O (1)? нам не нужно прибегать? 27.01.2019
  • @yantrab: это не список, это список пропуска. Удаление элемента требует обхода и потенциального изменения O(log N) разных слоев. 27.01.2019
  • @KevinChristopherHenry Я думаю, что удаление наименьшего элемента в списке пропуска занимает только O (1), потому что нужно удалить только первый элемент, а затем обновить заголовок, чтобы он указывал на все, на что указывает удаленный узел. 09.02.2019
  • @hutabalian: потенциально это необходимо сделать для каждого из O(log(N)) списки. 09.02.2019

    • 2

    Временная сложность доступа к любому элементу в отсортированном наборе по его счету составляет O (log (N)), следовательно, сложность команды.

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