Временная сложность пузырьковой сортировки
В пузырьковой сортировке n-1 сравнений будет выполнено на 1-й итерации, n-2 на 2-й итерации, n-3 на 3-й итерации и так далее. Таким образом, общее количество сравнений будет
(n-1)+(n-2)+(n-3)…….
сумма = n(n-1)/2
= o(n2)
Таким образом, временная сложность пузырьковой сортировки равна o(n2).
Временная сложность пузырьковой сортировки в лучшем случае будет o(n).
Временная сложность сортировки вставками
Если мы внимательно посмотрим на код сортировки вставками, то заметим, что каждая итерация цикла while уменьшает одну инверсию. Цикл while выполняется, только если i › j и arr[i] ‹ arr[j]. Поэтому общее количество итераций цикла while (для всех значений i) равно количеству инверсий. Следовательно, общая временная сложность сортировки вставками составляет O (n + f (n)), где f (n) — счетчик инверсии. Если количество инверсий равно O(n), то временная сложность сортировки вставками в лучшем случае составляет O(n). В худшем случае может быть n*(n-1)/2 инверсий. Худший случай возникает, когда массив отсортирован в обратном порядке. Таким образом, временная сложность сортировки вставками в наихудшем случае составляет O(n2).
