Сколько сравнений делает сортировка вставки в уже упорядоченном массиве из 2 элементов?

Question

Наилучший сценарий сортировки вставки должен быть O (n), однако, если у вас есть два элемента в массиве, которые уже отсортированы, например 10 и 11, не только он делает только одно сравнение, а не 2 ?

Answer 1

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

Самый лучший сценарий для сортировки вставки - это когда вы можете вставить новый элемент после всего лишь одного сравнения. Это может произойти только в 2 случаях:

• Вы вставляете элементы в с обратной сортировкой списка и сравнить новый элемент с первым элементом целевого списка.

• Вы вставляете элементы из отсортированного списка и сравниваете новый элемент с последним из списка целей.

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

Временная сложность была бы действительно O (n) для этих особых случаев. Вам не нужен такой благоприятный случай для этой сложности, временная сложность будет O (n), если существует постоянная верхняя граница для количества сравнений, не зависящих от длины списка.

Обратите внимание, что это обычная оптимизация для оптимизации и сортировки отсортированных списков. Если оптимизация, упомянутая во втором абзаце выше, не реализована, сортировка уже отсортированного списка будет наихудшим сценарием, с n сравнениями для вставки элемента n+1.

В общем случае, сортировка вставки по спискам имеет временную сложность O (N 2 ), но осторожно, реализация может произвести оптимальное решение для уже отсортированных списков.

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

Answer 2

Вставка сортировки N - 1 сравнение, если вход уже отсортирован.

Это потому, что для каждого элемента он сравнивает его с предыдущим элементом и что-то делает, если порядок не прав (не важно, что он делает сейчас, потому что порядок всегда прав). Таким образом, вы сделаете это N - 1 раз.

Похоже, вы должны понимать big O notation. Потому что O(n) не означает n операций, это даже не означает близко к n операциям (n/10^9 - это O (n), и это не очень близко к n). Все это означает, что функция приблизительно линейна (думайте об этом как о пределе, где n-> inf).