АиСД S01E07. Стеки, очереди. Амортизированное время

Алгоритмы и структуры данных. Семестр 1. Лекция 7.

На седьмой лекции мы поговорили о том, что такое амортизированное время работы, зачем оно нужно и как его измерять.

Университет ИТМО, 2019 г.

[elekka]

Почему при push и переполнении первого массива(n)*который стек* мы создаем массив(2n) и копируем за 0(n) туда элементы первого массива, если можно при i > n идти в другой массив.Например, создать vector<vector<int>>a(n) и ходить в a[i/n] вектор при каждом i и там уже смотреть a[i/n][i%n] ? Памяти столько же, а работает push за 0(1)
(тайминг примерно 13:00)

[izewer]

Это может показаться странным, но лекции для школьников проведенные Андреем Станкевичем в 2013 более полно описывают элементарные структуры данных, в особенности создание связки с решением практической задачи. А дэку куда ?

[nonatomicgames]

А 6я лекция 1 семестра будет? (Спасибо за всё, что выкладываешь!)