@zlodiak

Как происходит удаление из множества?

Известно, что чтобы удалить элемент из списка(list.remove(3)), возможно, придётся пройтись по всем его элементам. следовательно сложность рассчитывается как O(N)

Но сложность удаления элемента из множества(set.remove(3)), рассчитывается как O(1). Это мне не понятно, потому что множество так же как и список является неупорядоченной последовательностью.

Помогите пожалуйста понять как pythonу удаётся почти моментально найти удаляемый элемент в случае с множеством
  • Вопрос задан
  • 126 просмотров
Решения вопроса 1
@deliro
Множество — это почти тот же словарь. Там та же самая хэш-таблица. Только значений нет, есть только ключи. Соответственно, алгоритм поиска тот же — вычисляем хэш элемента, по нему определяем индекс в хэш-таблице за константное время и помечаем элемент как удалённый.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
28 мар. 2024, в 21:17
5000 руб./за проект
28 мар. 2024, в 20:46
150000 руб./за проект
28 мар. 2024, в 20:37
50000 руб./за проект