когда сортировка вставками выполняется быстрее, чем сортировка слиянием?

В качестве домашнего задания мне сказали, что сортировка вставками выполняется при 8n^2, а сортировка слиянием — при 64(n(lg n)). В рамках решения, которое мне дали, в нем говорилось, что сортировка вставками выполняется быстрее, чем сортировка слиянием, если n ‹ = 43, но ответ учителя на самом деле не объясняет, почему и как он пришел к 43. Кто-нибудь может это объяснить? Я не так уж хорош в вычислении времени выполнения, поэтому я пытаюсь лучше понять. И да, я пытался спросить учителя, но все равно был в замешательстве. Любая помощь будет здорово! спасибо!


runtime mergesort insertion-sort
person Lost    schedule 16.12.2012    source источник
comment
Пожалуйста, задавайте вопросы напрямую. Избегайте добавления историй.   -  person Sushant Gupta    schedule 17.12.2012
comment
ладно, можно. почему n ‹= 43?   -  person Lost    schedule 17.12.2012

Ответы (2)


arrow_upward
7
arrow_downward

Это произошло из этой (алгебраической) линии рассуждений

steps_in_insertion_sort <= steps_in_merge_sort
8n^2 <= 64n lg n
n^2 <= 8n lg n
n <= 8 lg n

Затем 43 работает методом проб и ошибок или путем решения для нуля уравнения n - 8 lg n = 0.

Для взлома методом проб и ошибок обратите внимание:

$ python
>>> 8 * log(43)/log(2)
43.41011803761678

Потому что «lg» означает логарифмическое основание по основанию два.

(Кроме того, подобные вычисления на самом деле не приводят к какому-либо реальному указанию на то, что один алгоритм превзойдет другой. Серьезно, ровно 43?)

person Ray Toal    schedule 16.12.2012
comment
Откуда 8n^2 <= 64n lg n? - person Pavel Podlipensky; 12.08.2014
comment
Эти значения пришли из вопроса. Я предполагаю, что 8 и 64 были произвольными значениями, присвоенными туманным константам, которые мы видим при выполнении асимптотического анализа, просто для того, чтобы задача имела некоторые конкретные значения. - person Ray Toal; 26.09.2015
comment
Я имел в виду, как математика работала в этом случае: n^2 <= 8n lg n? Но n^2 >= n lg n - person Pavel Podlipensky; 09.10.2015
comment
Для определенных значений n это будет <=, а для других значений n будет >=. Осталось найти отсечку. - person Ray Toal; 09.10.2015

arrow_upward
2
arrow_downward

Это второе упражнение в «Введении в алгоритмы», 3-е издание Кормена. Решение этого уравнения не так просто для новичка в алгоритмах:

Сортировка вставками лучше сортировки слиянием, когда 8n^2 ‹ 64n lg n , n ‹ 8 lg n , 2^ n/8 ‹ n . Это верно для 2 ‹= n ‹= 43 (найдено с помощью калькулятора). Следовательно, мы можем переписать сортировку слиянием, чтобы использовать сортировку вставками для входных данных размером 43 или меньше, чтобы улучшить время выполнения.

person Sahil Babbar    schedule 23.03.2014