Какова временная сложность dict.keys() в Python?

Я столкнулся с вопросом, когда решаю эту проблему с LeetCode. Хотя мое решение было принято системой, я по-прежнему не имею никакой идеи после поиска в Интернете по следующему вопросу: What is the time complexity of dict.keys() operation? Возвращает ли он ключи или реальный список (сохраняет в памяти) ключи?

Ответы

Ответ 1

В Python 2 это O (n), и он создает новый список. В Python 3 это O (1), но он не возвращает список. Чтобы нарисовать случайный элемент из dict keys, вам нужно преобразовать его в список.

Похоже, вы, вероятно, использовали random.choice(d.keys()) для части 3 этой проблемы. Если да, то это O (n), и вы поняли это неправильно. Вам нужно либо реализовать свою собственную хэш-таблицу, либо сохранить отдельный список элементов, не жертвуя вложениями и удалениями среднего размера O (1).