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

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

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

Деление чего-то на два обычно и означает 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)