Владстон Феррейра Фило - Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]

.

.

.

.

Шаг разбиения x.Функция merge_sort вызывается 2 xраз, каждый для списка из элементов: .

Все шаги разбиения имеют одинаковую сложность O ( n ). Временная сложность сортировки слиянием, следовательно, составляет x × O ( n ), где x — это количество шагов разбиения, необходимых для полного выполнения алгоритма [39] Мы не можем проигнорировать x , потому что это не константа. Если размер списка n удвоится, то нам потребуется еще один шаг разбиения. Если n увеличится в четыре раза, тогда нужны будут два дополнительных шага разбиения. .

Подсчет шагов.Как вычислить x ? Мы знаем, что рекурсивные функции заканчивают вызывать себя, как только достигают своего базового случая. Наш базовый случай — это одноэлементный список. Мы также увидели, что шаг разбиения x работает на списках из элементов. Потому:

Если вы не знакомы с функцией log 2, то не робейте! x = log 2 n — это просто еще один способ написать 2 x= n . Программисты любят логарифмический рост.

Посмотрите, как медленно растет количество требуемых шагов разбиения [40] Любой процесс, постепенно сокращающий объем входных данных на каждом шаге, деля его на постоянный делитель, требует логарифмического количества шагов до полного сокращения входных данных. с увеличением общего числа сортируемых элементов (табл. 3.1).

Временная сложность сортировки слиянием, следовательно, составляет log 2 n × O ( n ) = O ( n log n ). Это колоссальное улучшение по сравнению с сортировкой выбором O ( n 2). Помните разницу в производительности между линейно-логарифмическими и квадратичными алгоритмами, которые мы видели в предыдущей главе на рис. 2.4? Даже если предположить, что алгоритм O ( n 2) будет обрабатываться быстрым компьютером, в конечном счете он все равно окажется медленнее, чем алгоритм O ( n log n ) на слабой машине (табл. 3.2).

Убедитесь сами: напишите алгоритмы сортировки с линейно-логарифмической и квадратичной сложностью, а затем сравните их эффективность на примере случайных списков разного размера. Когда объемы входных данных огромны, такие улучшения часто оказываются необходимы.

А теперь давайте разделим и осилим задачи, в отношении которых мы раньше применяли полный перебор.

Для задачи о самой лучшей сделке (см. раздел «Полный перебор» ) подход «Разделяй и властвуй» оказывается лучше, чем решение «в лоб». Разделение списка цен пополам приводит к двум подзадачам: нужно найти лучшую сделку в первой половине и лучшую сделку во второй. После этого мы получим один из трех вариантов:

1) лучшая сделка с покупкой и продажей в первой половине;

2) лучшая сделка с покупкой и продажей во второй половине;