Сложность времени выполнения сортировки вставками

Question

Сложность времени выполнения сортировки вставками

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

Авв

В худшем случае $j$ сравнения необходимы для вставки $jth$ элемент в правильное положение. Для алгоритма сортировки вставками сложность времени выполнения будет $\mathcal{\Theta}(n^2)$ для количества сравнений следующим образом:

2 + 3 + ... + н "=" \frac{н (н - 1)}{2} - 1

$2+3+\textit{...}+n=\frac{n(n-1)}{2}-1$

Вопрос : Почему количество сравнений начинается с $2$ выше, хотя я думаю, что это должно начинаться с $1+2+3\textit{...}$ ?

Трэвис Джей

Здесь есть вопрос?

Авв

@ТрэвисДж. Я не правильно сформулировал вопрос. Я имел в виду, почему количество сравнений начинается с

2

$2$ нет

1

$1$ ?

Ответы (1)

Сложность времени выполнения сортировки вставками

@ТрэвисДж. Я не правильно сформулировал вопрос. Я имел в виду, почему количество сравнений начинается с $2$ нет $1$ ?

Фикар · Answer 1

Потому что он делает это дважды. Сначала спрашивает: есть $a_2>a_1,$ ответ да, тогда так и есть $i=i+1,$ так $i=2$ то и дело спрашивает $a_2>a_2.$ ложно и ломается.

Как видите, было два сравнения.

Сложность времени выполнения сортировки вставками

Авв

Трэвис Джей

Авв

Ответы (1)

Фикар

Ожидаемое время быстрой сортировки

Как оценить затраченное время? (темпы роста)

Нахождение дополнения множества путем отрицания логических утверждений

Почему найти хроматическое число сложно?

Как определить сложность класса дискретной математической задачи?

Использование mergesort merge() для сортировки k упорядоченных массивов

Сложность алгоритма — цикл for внутри цикла while; уменьшается в 2 раза

Вероятность того, что два конкретных элемента сгруппированы в случайном разделе с фиксированными размерами

Какова временная сложность при равномерной выборке записей bbb без замены записей nnn?

Связный максимальный граф GGG без циклов длины не менее k+1k+1k+1 имеет |V(G)|≤k|V(G)|≤k|V(G)| \leq k или имеет вершину-сечение, когда k≥2k≥2k \geq 2