почему вставка сортировки в лучшем случае большая O сложность O (n)?
Ниже приведен мой код сортировки вставки:
void InsertionSort(vector<int> & ioList)
{
int n = ioList.size();
for (int i = 1 ; i < n ; ++i)
{
for (int j = 0 ; j <= i ; ++j)
{
//Shift elements if needed(insert at correct loc)
if (ioList[j] > ioList[i])
{
int temp = ioList[j];
ioList[j] = ioList[i];
ioList[i] = temp;
}
}
}
}
Средняя сложность алгоритма O (n ^ 2).
Исходя из моего понимания больших обозначений O, это происходит потому, что в этом случае мы запускаем два цикла (внешний n-1 раз и внутренний 1,2, … n-1 = n (n-1) / 2 раза и, таким образом, результирующая бессимптомная сложность алгоритма O (n ^ 2).
Теперь я прочитал, что лучший случай — это случай, когда входной массив уже отсортирован.
И большая O сложность алгоритма в этом случае O (n). Но я не понимаю, как это возможно, поскольку в обоих случаях (в среднем и в лучшем случае) мы должны выполнять циклы одинаковое количество раз и сравнивать элементы. Единственное, чего избегают — это смещение элементов.
Таким образом, вычисление сложности также включает в себя компонент этой операции обмена?
Решение
Да, это потому, что ваша реализация неверна. Внутренний цикл должен отсчитываться от i-1 до 0и он должен завершиться, как только найдет элемент ioList[j] это уже меньше, чем ioList[i],
Именно из-за этого критерия завершения алгоритм выполняет за O (n) время в лучшем случае:
Если входной список уже отсортирован, внутренний цикл немедленно прекратится для любого iто есть количество выполненных вычислительных этапов заканчивается пропорциональностью количеству выполнений внешнего цикла, то есть O (n).
Другие решения
Ваша реализация «сортировки вставок» оставляет желать лучшего.
В вашем внутреннем цикле вы не должны сканировать весь путь до i-1 поменять местами каждый элемент больше ioList[i], Вместо этого вы должны отсканировать назад от i-1 пока вы не найдете правильное место для вставки нового элемента (то есть, пока не найдете элемент, меньший или равный новому элементу), и вставите его туда. Если входные данные уже отсортированы, то правильная точка вставки всегда находится сразу, и внутренний цикл не выполняется i-1 раз, он выполняется только один раз.
Ваша сортировка также хуже, чем вставка сортировки в среднем, так как вы всегда делать i+1 операции для каждой итерации внешнего цикла — некоторые из этих операций — просто сравнение, а некоторые — сравнение, за которым следует своп. Сортировка вставки должна выполнять в среднем только половину, так как для случайного / среднего ввода правильная точка вставки находится на полпути через начальный отсортированный сегмент. Также возможно избежать перестановок, так что каждая операция представляет собой сравнение плюс копию.