Может ли кто-нибудь объяснить, почему сортировка вставки имеет временную сложность Θ (n²)?Сложность времени вставки Сортировка
Я вполне уверен, что я понимаю временную сложность как концепцию, но я действительно не понимаю, как применить ее к этому алгоритму сортировки. Должен ли я просто искать математические доказательства, чтобы найти этот ответ?
В среднем каждая вставка должна пересекать половину отсортированного списка, делая одно сравнение за шаг. Список растет каждый раз.
Итак, начиная со списка длины 1 и вставляя первый элемент, чтобы получить список длины 2, мы имеем средний обход .5 (0 или 1) мест. Остальные - 1.5 (0, 1 или 2 место), 2.5, 3.5, ..., n-.5 для списка длины n + 1.
Это простая алгебра, 1 + 2 + 3 + ... + n - n * .5 = (n (n + 1) - n)/2 = n^2/2 = O (n^2)
Обратите внимание, что это средний случай. В худшем случае список должен быть полностью пройден (вы всегда вставляете следующий наименьший элемент в восходящий список). Тогда у вас есть 1 + 2 + ... n, который все еще O (n^2).
В лучшем случае вы найдете точку вставки в верхнем элементе с одним компартом, поэтому у вас есть 1 + 1 + 1 + (n раз) = O (n).
Хороший ответ. Я просто хочу добавить 2 вещи: 1. Хороший набор заметок Питера Крамминса существует здесь http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-one/ 2. В В худшем случае у нас самые коварные входы. Это список полностью сортируется по-разному. Поэтому каждая итерация будет проходить через «j». Формула для вычисления времени T (n) = sum (\ theta (j)) для j = 2: n. (при условии, что список индексируется с 1) – hAcKnRoCk
@MhAcKN Точно. Вот почему реализация сортировки для больших данных уделяет пристальное внимание «плохим» случаям. Вы _generally_ (и это очень грубое эмпирическое правило) не хотят использовать сортировку вставки, если данные могут вырасти до более чем ста или около того. – Gene
Спасибо, ген. Разрабатывал временную сложность теоретически, и я ломал себе голову, что фактически определяет Theta в асимптотической нотации. Поэтому я предполагаю, что он количественно определяет количество пройденных обходов. Просто небольшое сомнение в том, что произойдет, если операторы> или = реализованы более эффективным образом в одном из типов вставки. Тогда как мы можем изменить обозначение Theta(), чтобы отразить это. или я передумал? – hAcKnRoCk
Он применяется только к массивам/спискам - т. Е. Структурам с временем O (n) для вставки/удаления. Он может быть другим для других структур данных. Например, для skiplists это будет O (n * log (n)), потому что бинарный поиск возможен в O (log (n)) в skiplist, но insert/delete будет постоянным.
Написание математического доказательства самостоятельно только укрепит ваше понимание. Часто самые сложные части - это на самом деле настройка. Например, сначала вы должны уточнить, хотите ли вы наихудшую сложность алгоритма или что-то еще (например, сложность среднего размера). Во-вторых, вы хотите определить, что считается фактической операцией в вашем анализе. Для алгоритмов сортировки на основе сравнения, таких как сортировка вставки, обычно мы определяем сравнения, чтобы принимать «O (1)» время и свопы, чтобы взять «O (1)» время. Вы можете оправдать себя, является ли это допустимой метрикой. С этого момента просто примените определение – rliu