Python-сообщество

py.user.next
поиск во множестве - O(1)

O(1) - это все-таки когда нет зависимости от n. В нашем случае она все же есть и равна примерно O(log(n)).

Isem
В нашем случае она все же есть и равна примерно O(log(n)).

чего ?

Isem
py.user.next
давайте разовьем эту тему, матчасть в студию! :-)

py.user.next
чего ?

Это что, удивление от незнания, выраженное в родительном падеже?

Isem
Это что, удивление от незнания, выраженное в родительном падеже?

это вопрос, где ты там logn нашёл ? у множества поиск занимает O(1) при любом количестве элементов

py.user.next
это вопрос, где ты там logn нашёл ? у множества поиск занимает O(1) при любом количестве элементов

Это обращение к элементу массива занимает O(1), то есть не зависит от количества элементов, а поиск элемента в сортированной коллекции занимает O(log(n)) времени. Это очевидно для бинарного поиска. Количество сравнений, которое нужно сделать, равно log2(n) и мы заменяем логарифм по основанию 2 на натуральный логарифм, так как константный множитель не играет роли. И не важно, что в питоне используется хэш функция, она лишь влияет на коэффициент при логарифме, который мы игнорируем.

Isem
Это обращение к элементу массива занимает O(1)

к элементу вектора

Isem
а поиск элемента в сортированной коллекции занимает O(log(n)) времени

множество - динамическая структура данных, общая для всех языков
словарь в питоне - нагруженное множество
и поиск в них занимает всегда одно и то же время, даже если там 1000000 элементов
(реализуется через хеш-таблицу)

Не спорьте, девочки, читайте первоисточник :)

py.user.next
и поиск в них занимает всегда одно и то же время, даже если там 1000000 элементов
(реализуется через хеш-таблицу)

Я внятно выразился, что хэш функция влияет лишь на коэффициент при логарифме. Для большой области значений хэш функции (например, 65536), и при n < 65536 скорость алгоритма поиска в множестве равна O( log(n)/log(65536) ),что при n < 65536 дает O(1). При n -> бесконечность, что по ссылке

Lexander
Не спорьте, девочки, читайте первоисточник :)

английским по-белому написано, что в худшем случае - это O(n), что гораздо хуже, чем O( log(n) ). Но как правило (читаем второе предложение с начала) “However, it is generally safe to assume that they are not slower by more than a factor of O(log n).”
Если у вас до сих пор крадутся сомнения, кто вам мешает создать множество из четных чисел размером несколько миллионов элементов и потренироваться в поиске случайного элемента с замером времени?

py.user.next
Isem
Это обращение к элементу массива занимает O(1)

py.user.next
к элементу вектора

Что вы тут подчеркнули, имеющее отношение к сути вопроса?

Isem
Что вы тут подчеркнули, имеющее отношение к сути вопроса?

ты не отличаешь множество в питоне от множества как структуры данных
в питоне множество - это одна из реализаций множества, её могут и через n сделать
то же самое насчёт массива: массив - это реализация вектора как структуры данных
кстати, список представляет из себя динамический вектор, кортеж - вектор, словарь - нагруженное множество

Isem
что при n < 65536 дает O(1)

при любом количестве она должна давать O(1), потому что перебор элементов не требуется
представь, что ты множество записал в вектор, какова будет скорость поиска ?
там и написано, что скорость равна O(1), просто у них в реализации она может не равняться O(1), потому что реализация такая

так что никакого log n