Почему O (n) nlogn время выполнения для вставки сортировки идеала?

Question

Мы изучали в классе, что сортировки вставки - это омега линейное время выполнения (если передано уже отсортированный массив) и Big-O O (n^2) для всех остальных случаев. Затем наш профессор начал опираться на идеал для сортировки вставки, имеющий подход «сортировки слияния» и что идеальным было бы использовать сортировку слияния и иметь время выполнения O (nlogn)? Он не очень ясный человек ... вообще. Вы можете объяснить, что он имел в виду, пожалуйста!

Answer 1

Возможно, у меня есть представление о том, что мог сказать ваш профессор. Для массивов очень малых порядков (или просто посмотреть, отсортирован ли массив), возможно, имеет смысл запустить insertion sort, поскольку он не потребляет дополнительного пространства и работает в линейном времени. Опубликуйте, что вы будете запускать сортировку слиянием, которая будет равна nlog(n) независимо от условий (если вы не используете Natural Merge Sort, и в этом случае ваш лучший случай сводится к O (n), и это делает еще меньше смысла для запуска этого алгоритма сортировки вставки), а также для использования и вспомогательного пространства O (n).

Как хорошо, может быть, стоит отметить, что язык, подобный Java, использует алгоритм быстрой сортировки с двойным поворотом вместо сортировки слияния (худший случай быстрой сортировки - это O (n^2)). Я не совсем уверен в этом, но это можно объяснить тем, что быстрый сортировка использует меньшее вспомогательное пространство, но тем более, потому что не очень часто встречается массив, который попадает в худший случай.

Answer 2

O (N) считается быстрым, O (N Log (N)) справедливым и O (N²) медленным.

Для небольшого количества элементов вам может быть все равно. Но подумайте о сортировке миллиона элементов: время будет пропорционально 1000000 (скажем, 1 мс), 20000000 (20 мс) и ... 1000000000000 (11 недель).

Именно поэтому алгоритмы сортировки O (N²) часто избегают, зная, что O (N Log (N)) возможен во всех случаях и O (N) для некоторых конфигураций.

Answer 3

Давайте посмотрим.

вставки рода имеет O (N^2) Время работы

Это ясно, что сортировка вставкой работает на O (N^2). Вы можете больше узнать об этом here.

Наш профессор затем начал волочился об идеале для вставки рода, имеющая «сортировка слияния» подход

Я думаю, что вы пытались сказать idea и не ideal. Давайте посмотрим на это idea на сортировку вставки, имеющую подход «слияния». Основной вид слияния - это парадигма разделения и покорения. Итак, давайте предположим, что у меня есть этот массив

Having вставки рода с «сортировка слиянием» подход сделает этот массив в двух региональных (или более) базы по разделяй и покорить парадигму.

6 5 4 | 3 2 1

После этого мы можем применить сортировку вставки на каждой стороне региона, а затем использовать conquer для их объединения.

4 5 6 | 1 2 3

Ну, а теперь давайте посмотрим на IF мы применим неравенство к каждому элементу массива.

6 | 5 | 4 | 3 | 2 | 1

ПОДОЖДИТЕ МИНУТ, разве это не сортировка слияний? Яп, поэтому ваш сенсей сказал

, что идеальным было бы использовать сортировки слиянием и есть O (N журнал N) во время выполнения

На самом деле, некоторые реализации на слиянии сортировки используется вставку sort, когда активируется порог (например, имеет только 7 элементов). Вы можете прочитать его here.