Средняя (амортизированная) алгоритмическая сложность — это оценка времени работы алгоритма, усреднённая по всем возможным входным данным или по последовательности операций. Она показывает, сколько ресурсов (времени, памяти) алгоритм потребует в среднем, а не в худшем или лучшем случае.

Примеры алгоритмов с разной сложностью:

O(1) — константное время. Например, доступ к элементу массива по индексу.
O(log n) — логарифмическое время. Например, бинарный поиск в отсортированном массиве.
O(n) — линейное время. Например, поиск элемента в неотсортированном массиве.
O(n log n) — например, быстрая сортировка (quicksort) в среднем случае.
O(n²) — квадратичное время. Например, сортировка пузырьком.

Пример амортизированной сложности:

В структуре данных "динамический массив" (например, slice в Go или ArrayList в Java) операция добавления элемента обычно O(1), но при переполнении массива происходит перераспределение памяти и копирование элементов, что занимает O(n). Амортизированная сложность добавления остаётся O(1), так как перераспределение происходит редко.

// Пример амортизированной сложности добавления в ArrayList
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i); // обычно O(1), иногда O(n) при расширении
}

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

Что такое средняя алгоритмическая сложность? Можешь рассказать и привести примеры алгоритмов с разной сложностью?