в этом видeо увидел на 0:45 - 0:56 то, что нужно отсортировать половинки массива, но автор не указал как. По идее, время выполнения сортировки слиянием равно n*log(n)
, но что, если два этих половинных массивов мы будем сортировать разными методами? Тогда, вроде, не будет достигнуто заявленное время (как мне кажется).
Вопрос: каким методом нужно сортировать два "половинных" массива?
1 ответ
Идея именно в том, что каждая половинка сортируется тем же методом - сортировкой слияния. Именно отсюда и вытекает сложность алгоритма O(N*log(N)).
Что до рекурсия-итерация: да, в общем случае рекурсия медленнее (не в смысле сложности алгоритма!) из-за вызова функции, но эта разница не так уж велика, а оптимизатором часто просто убирается вовсе.
fact(int number) { if number == 1 return 1; return number * fact(number -1); }
имеет точно такую асимптотику, как и цикл. По сути, тут цикл заменен рекурсией. см Хвостовая рекурсия