Имеет ли сортировка вставками значение Θ(n)?

Краткий ответ, да, это так. Биг-Тета всегда существует. Вопросы: Вы говорите о лучшем, худшем или среднем случае? и Можете ли вы это доказать?

Лучший случай и худший случай — это не то же самое, что Big-O или Big-Theta. В лучшем случае это Big-Theta. В худшем случае другая Big-Theta. Они разные.

Позвольте мне объяснить различие, которое я делаю.

Дело против связанного

Люди, занимающиеся анализом сложности, обычно очень небрежны в своих обозначениях. Это отличный вопрос, где стоит быть точным. Случай и граница - разные, ортогональные понятия. Очень важно не смешивать их.

• Случай: лучший, худший, средний.
• Граница: верхняя граница (O), нижняя граница (Ω), точная граница (Θ)

Каждый из кейсов имеет свои собственные границы. Когда вы анализируете сложность алгоритма, вам нужно сначала определить, какой случай вы анализируете. Вы ищете лучшую производительность корпуса? Худший случай? Средний случай?

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

Свободные границы

Важно понимать, что не существует единственных верхних или нижних границ. Их много. Например, давайте рассмотрим наихудший случай производительности сортировки вставками. Он имеет много нижних границ и много верхних границ.

• Установить нижнюю границу Ω(1) несложно. Я имею в виду, что у каждого алгоритма есть постоянная нижняя граница. Это не всегда жесткая нижняя граница, но это нижняя нижняя граница.
• Точно так же можно начать с очень слабой верхней границы O(n!). Именно столько времени потребовалось бы, если бы вы просто перебирали каждую перестановку входного списка, пока не наткнулись бы на отсортированный. Это худший алгоритм сортировки в мире. Конечно, сортировка вставками работает лучше, верно?

Жесткие границы

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

• Ω(n) будет более точной нижней границей, чем Ω(1). И было бы легко доказать Ω(1): алгоритм сортировки, безусловно, должен проверять каждый элемент входного списка, что занимает линейное время. Если мы это докажем, то узнаем, что наихудшая производительность сортировки вставками — это не только Ω(1), но и Ω(n).
• Как вы сказали, хорошо известно, что производительность в худшем случае имеет верхнюю границу O(n²). Это гораздо более точная верхняя граница, чем O(n!).

Равные границы

Если вы сможете доказать, что нижняя и верхняя границы совпадают, вы получите точную оценку Θ. Большая Тета. Для этого вам нужно сжать верхнюю и нижнюю границы вместе, пока они не сойдутся в точном правильном ответе.

• Мы знаем, что O(n²) — это максимально точная верхняя граница.
• Таким образом, чтобы получить Θ, нам нужно сузить нижнюю границу до Ω(n²). Доказательство этого на самом деле не является целью этого ответа, поэтому давайте просто предположим, что мы это сделали.

Если мы сможем доказать, что производительность сортировки вставками в наихудшем случае составляет в лучшем случае Ω(n²) и в худшем случае O(n²), то мы знаем, что она точно Θ(n²).

Несколько Θ

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

Если бы вы это сделали, вы бы получили три ответа. Три больших теты.

• Лучший вариант: Θ(n)
• Худший случай: Θ(n²)
• Средний случай: Θ(n²)

На самом деле, вы могли бы даже придумать больше Big-Thetas. Лучший, худший и средний случай — не единственные случаи, которые можно анализировать. Конечно, они самые распространенные, но я могу представить и другие, которые будут иметь свои собственные нижние и верхние границы.