Временная сложность методов сортировки

Методы "пузырька", вставками и посредством выбора имеют временную сложность О(п²) и W(n ²) на последовательностях из п элементов.

Рассмотрим листинг метода "пузырька". Независимо от того, что подразумевается под типом recordtype, выполнение процедуры swap требует фиксированного времени. Поэтому строки (3), (4) затрачивают с₁ единиц времени; c₁ — некоторая константа. Следовательно, для фиксированного значения i цикл строк (2) - (4) требует не больше с₂(n - i) шагов; с₂ — константа. Последняя константа несколько больше константы с₁, если учитывать операции с индексом j в строке (2). Поэтому вся программа требует

шагов, где слагаемое с₃п учитывает операции с индексом i в строке (1). Последнее выражение не превосходит (с₂/2 + с₃) n ² для п > 1, поэтому алгоритм "пузырька" имеет временную сложность О(п²). Нижняя временная граница для алгоритма равна W(n ²), поскольку если даже не выполнять процедуру swap (например, если список уже отсортирован), то все равно п(п - 1)/2 раз выполняется проверка в строке (3).

Сортировка вставками. Цикл while в строках (4) - (6) выполняется не более O(i) раз, поскольку начальное значение j равноp i, а затем j уменьшается на 1 при каждом выполнении этого цикла. Следовательно, цикл for строк (2) — (6) потребует не более шагов для некоторой константы с. Эта сумма имеет порядок О(п²).

Можно показать, что если список записей первоначально был отсортирован в обратном порядке, то цикл while в строках (4) - (6) выполняется ровно i – 1 раз, поэтому строка (4) выполняется раз. Следовательно, сортировка вставками в самом худшем случае требует времени не менее W (n ²). Можно показать, что нижняя граница в среднем будет такой же.

Сортировка посредством выбора, (см. соответствующий листинг). Легко проверить, что внутренний цикл в строках (4) - (7) требует времени порядка О(п - i), поскольку j здесь изменяется от i + 1 до п. Поэтому общее время выполнения алгоритма составляет для некоторой константы с. Эта сумма, равная сп(п - 1)/2, имеет порядок роста О(n ²). С другой стороны, нетрудно показать, что строка (4) выполняется не менее раз независимо от начального списка сортируемых элементов. Поэтому сортировка посредством выбора требует, времени не менее W (п²) в худшем случае и в среднем.