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

Question

из redis doc:

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

Сложность времени: O (log (N) * M), где N - количество элементов вотсортированный набор, а M - количество вытолкнутых элементов.

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

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

Answer 1

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

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

Answer 2

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