Каково время выполнения сортировки вставкой, если каждый элемент во входном массиве, скажем, не более чем на 10 позиций?

Question

Каково время выполнения сортировки вставкой, если каждый элемент во входном массиве, скажем, не более чем на 10 позиций не по месту?

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

Answer 1

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