46
правок
Изменения
Нет описания правки
=Время работы=
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> - время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение: