Уведомления

Группа в Telegram: @pythonsu

#1 Апрель 9, 2021 14:26:18

pojiratel2000100
Зарегистрирован: 2021-04-09
Сообщения: 1
Репутация: +  0  -
Профиль   Отправить e-mail  

Как получается время О(n*logn) при быстрой сортировке.

Как я понимаю, (со скрина ниже) что количество стеков это logn, и у нас в каждом стеке в среднем мы обращаемся к n элементам массива, но по сути, как я понимаю, стеков открывается больше logn. Просто одни стеки закрываются, другие наоборот открываются и в среднем число открытых стеков получается logn(мои субъективные рассуждения, прошу поправить где не так). Почему именно к n элементам мы будем в среднем обращаться на каждом стеке?

Прикреплённый файлы:
attachment Скриншот 09-04-2021 141056.jpg (38,0 KБ)

Офлайн

#2 Апрель 9, 2021 23:22:56

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 8138
Репутация: +  733  -
Профиль   Отправить e-mail  

Как получается время О(n*logn) при быстрой сортировке.

Деление чего-то на два обычно и означает logN при измерении сложности алгоритма. Если логарифм имеет основание 2, то log2(n) задаёт формулу для вычисления количества разбиений на два. В телефонной книге, упорядоченной по алфавиту, есть 1000 страниц, значит, при поиске телефонного номера по фамилии максимальное число открываний этой книги посередине равно log2(1000). Это число 9.96578428466 , которое мы округляем до 10. Значит, за десять открытий или меньше ты по фамилии найдёшь номер телефона или его отсутствие. При измерении временной сложности алгоритма неважно, какое основание у логарифма, так как задача состоит в том, чтобы определить к какой из известных сложностей относится алгоритм. Поэтому для каждого основания логарифма это разбиение на виды сложностей алгоритма будет всегда одинаковым, хоть 2 там будет, хоть 10, хоть e. Поэтому основание логарифма и не пишут. Когда читаешь log, подразумевай там основание логарифма 2. То есть читаешь logN, а подразумеваешь log2(N). Со временем ты не будешь этим заморачиваться, а будешь сразу видеть сложность (их там всего несколько штук в районе десятка). Надо только знать, что бывают необычные сложности типа N^1.2 - то есть это не N и не N^2, а что-то между ними, близкое к N, но не настолько, чтобы считать это за N.



Отредактировано py.user.next (Апрель 9, 2021 23:26:39)

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version