Сколько раз вызывается метод resize ()?

Question

Не могли бы вы объяснить, почему правильный ответ является логарифмическим? Я не понял.

Предположим, что, начиная с пустой структуры данных, мы выполняем n операции push в нашей реализации стека с изменяющимся размером массива. Сколько раз вызывается метод resize()?

а) постоянная

b) логарифмический (правильный). Метод resize() вызывается только в том случае, если размер стека равен степени 2. Имеется ~ log2n степеней 2 от 1 до n.)

в) линейный

г) квадратичный

Answer 1

Чтобы разместить новый элемент, полностью заполненный динамический массив (или resizing-array, как вы его называете) удваивает свою емкость при нажатии на новый элемент. Это верно для большинства распространенных реализаций динамического массива.

Изначально ваш стек (реализованный через динамический массив) пуст. Когда вы нажимаете первый элемент, его размер изменяется до 1 элемента. Когда вы нажимаете секунду, он изменяет размер до 2 элементов. Когда вы нажимаете третье, он изменяет размер до 4 элементов. Таким образом, для 4-го элемента нет изменения размера. Но когда вы нажимаете 5-й, он теперь изменяет свой размер до емкости 8. И так далее.

То есть, если вы нажимаете n элементы, resize() будет вызываться при нажатии на 1-й, 2-й, 3-й, 5-й, 9-й, 17-й, ..., элементы.

Так сколько раз resize() вызывается? Если вы игнорируете 1-й элемент, вызывается resize() при нажатии (2^k + 1)th элементов, где k = 0,1,2,3,4,5.... Поскольку в диапазоне [1,n] таких номеров почти log2(n), это будет количество вызовов resize(). Следовательно, логарифмический является правильным ответом.