Я не знаю о точной реализации Redis.Однако если отсортированный набор реализован с использованием списка пропусков, удаление займет O(log n).
Из наблюдений о том, как создаются списки пропусков, я думаю, что вы можете понять идею.Это не реализовано с использованием простого единственного массива, который займет O(m) время для удаления первых m элементов.Вместо этого он использует несколько массивов (представьте, что это связанный список) и сохраняет значения, чтобы поддерживать добавление / удаление / поиск во время O(log n).
Если это было реализовано с использованием одного массива, то вы правы - удаление должно занять O(m) времени.Однако это не относится к спискам пропуска.Я пытаюсь добавить изображение, откуда вы можете иметь представление о том, как строятся списки.
Надеюсь, это поможет!
Обновление
Имейте в виду, что в списке пропуска есть уровни.Максимальное количество уровней, которое может иметь список пропусков, составляет O(log n).Давайте рассмотрим удаление первых трех элементов здесь (т.е. 12, 17, 20).Чтобы сначала удалить 12, мы должны изменить уровень 2 и уровень 1, так как мы должны указать - ∞ на 17 на обоих уровнях.Как только 12 удаляется, мы удаляем 17 и делаем то же самое и здесь.Для каждого удаления нам может потребоваться выполнить итерацию не более O(log n) уровней, как указано выше относительно максимального количества уровней.Я надеюсь, вы поняли идею.