Какова амортизированная сложность push_back у динамического массива при удвоении ёмкости и почему?
O(1) амортизированно. Редкие дорогостоящие копирования «распределяются» на множество дешёвых вставок; потенциал/агрегатный анализ показывает, что суммарная стоимость m операций ≤ 3m. Кстати, у нас сейчас действует 40% скидка на курс Алгоритмы и структуры данных.
Библиотека собеса по Python
Post #1248
836