origami1024
@origami1024
went out for a night walk

Какова алгоритмическая сложность преобразования массива в set, через Set(array)?

Решаю задачки, непонятно, как учесть сложность преобразования array в set.
По идеи Set() проходится циклом по всем элементам, тоесть добавляет O(n).
Или же он как-то работает напрямую с памятью?
  • Вопрос задан
  • 184 просмотра
Решения вопроса 2
longclaps
@longclaps
Напрямую, накривую - какое отношение это имеет к алгоритмической сложности?
O(n).
Ответ написан
uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel
Нужно сделать set.Add() для всех элементов array - это дает O(n). set.Add() проверяет на уникальность - это в прямолинейном исполнении еще O(n). Конечно на всех современных движках Set оптимизирован до HashTable. В идеальном мире HashTable.Add имеет сложность O(1), но мы же не в идеальном, на практике думаю можно рассчитывать на O(log(n)) с учетом небходимых периодических аллокаций с ростом Set. Таким образом, по моим сугубо личным, бездоказательным оценкам, рассчитывать можно на O(n*log(n))
И, да, я убежден что быстрее O(n) быть не может. Преобразовать последовательный массив в хештаблицу быстрее O(n) невозможно даже теоретически.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@tumbler
бекенд-разработчик на python
Вопрос в том, в каких операциях считать сложность.
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы