Какая математическая методика используется для сравнения сложности алгоритма?

Question

Я начал читать «Введение в алгоритмы» сегодня, но я немного запутался из-за одного из упражнений.

В упражнении 1.2.2 задается вопрос читателю

Предположим, мы сравниваем реализации сортировки слиянием и сортировки вставкой на одном компьютере.Для входных данных размера n сортировка вставки выполняется за 8n ^ 2 шагов, а сортировка слиянием - за 64n log n шагов.

Для каких значений n сортировка вставки бьет сортировку слиянием?

Сначала я попытался открыть Wolfram Alpha и использовать его для построения графиков уравнений, но я не смог точно сравнить два графика.

Затем я попытался выбрать случайное значение для n (200), работаявыписать уравнения на бумаге, а затем изменить значение n на основе моих результатов.
Но это заняло слишком много времени.

Как правильно решить это упражнение?

Answer 1

См. здесь : 8 n ² = 64 n log ₂ n .Просто поместите обе вещи в одно уравнение.

То есть, примерно n = 43 является пределом полезности вставки сортировки здесь.

Обычно вы решаете это, решая вышеуравнение f ( n ) = g ( n ) путем решения f ( n * 1030)*) - g ( n ) = 0, однако аналитический результат в этом случае не очень хорош, поскольку вы смешиваете многочлен с логарифмической функцией.Я бы просто попробовал несколько значений и посмотрел, где результат меняется с положительного на отрицательный.Как только у вас есть один положительный и один отрицательный моменты, вы можете использовать бисекцию, чтобы сузить ее.

Метод грубой силы состоит в том, чтобы просто опробовать все n до определенной точки.Вы уже знаете, что алгоритмы O ( n ² ) не подходят для больших наборов данных, поэтому n должно быть довольно маленьким.Для моего тестирования это выглядело так:

PS Home:\> function lb($n){[math]::Log($n)/[math]::Log(2)}  # binary logarithm
PS Home:\> 1..80 | %{,($_,(8*$_*$_),(64*$_*(lb $_)))} | %{"{0}: delta={3}, I={1}, M={2}" -f $_[0],$_[1],$_[2],($_[2]-$_[1])}
...
38: delta=1210,9597126948, I=11552, M=12762,9597126948
39: delta=1024,36393828017, I=12168, M=13192,3639382802
40: delta=824,135922911648, I=12800, M=13624,1359229116
41: delta=610,216460117852, I=13448, M=14058,2164601179
42: delta=382,549232429308, I=14112, M=14494,5492324293
43: delta=141,080604940173, I=14792, M=14933,0806049402
44: delta=−114,240561917371, I=15488, M=15373,7594380826
45: delta=−383,463082570537, I=16200, M=15816,5369174295
46: delta=−666,633601368154, I=16928, M=16261,3663986318
47: delta=−963,796734153668, I=17672, M=16708,2032658463
48: delta=−1274,99519778461, I=18432, M=17157,0048022154
...

(Извините за ужасный код; это был просто очень быстрый дудл.)

Answer 2

Есть ли какое-то значение n, где они равны?

Что происходит выше этой точки? Ниже?

Answer 3

Решая уравнение 8n² < 64n lg n, приходим в уравнение 2^(n/8) - n < 0.

Когда я не был на тесте, просто выполнял некоторые упражнения, я использовал инструмент, чтобы увидеть график f(n) = 2^(n/8) - n.

Как здесь задано, не существует натурального числа n, где сортировка вставки имеет то же время, что и сортировка слиянием, и для f(n) < 0 мы получили:

2 <= n <= 43. </p>

Надеюсь, это кому-нибудь поможет :)

Answer 4

Для n · 43, 8n2 · 64n log n и сортировки вставки сливаются сортировки слияния Хотя сортировка слиянием выполняется в £ (n log n) времени наихудшего случая, а сортировка вставки выполняется в £ (n2) наихудшем случае время, постоянные факторы в сортировке вставки делают это быстрее для маленького n. Поэтому имеет смысл использовать сортировка вставкой в ​​сортировке слиянием, когда подзадачи становятся достаточно маленькими. Рассмотрим модификацию сортировки слиянием, в которой подмассивы размером k или меньше (для некоторых k) не делятся дальше, а сортируются явно с сортировкой вставки.