0

в этом видeо увидел на 0:45 - 0:56 то, что нужно отсортировать половинки массива, но автор не указал как. По идее, время выполнения сортировки слиянием равно n*log(n), но что, если два этих половинных массивов мы будем сортировать разными методами? Тогда, вроде, не будет достигнуто заявленное время (как мне кажется). Вопрос: каким методом нужно сортировать два "половинных" массива?

13
  • Сортировкой слияния. В вашем видео об этом говорится на 5-ой минуте
    – EzikBro
    Commented 1 окт. 2020 в 18:06
  • а может просто разделить сразу массив из n элементов на n/2 массивов, где в каждом массиве, соответственно, 2 элемента (случай с четным кол-вом)? Да, конечно, пронумеровав эти массивы (засунув их в другой массив, а эти сделать подмассивами) Commented 1 окт. 2020 в 18:09
  • В нерекурсивной реализации примерно так и делается, однако сами попробуйте написать рекурсивную и нерекурсивную версии. Первую я могу написать за минуту, а вторую ни разу в жизни не писал вообще, а если бы пришлось, то убил бы кучу нервов
    – EzikBro
    Commented 1 окт. 2020 в 18:11
  • разве нерекурсивный метод не быстрее, чем рекурсивный? Commented 1 окт. 2020 в 18:12
  • 1
    я не знаю, какую реализацию вы имели ввиду, но простейшая вида fact(int number) { if number == 1 return 1; return number * fact(number -1); } имеет точно такую асимптотику, как и цикл. По сути, тут цикл заменен рекурсией. см Хвостовая рекурсия
    – tym32167
    Commented 1 окт. 2020 в 18:25

1 ответ 1

1

Идея именно в том, что каждая половинка сортируется тем же методом - сортировкой слияния. Именно отсюда и вытекает сложность алгоритма O(N*log(N)).

Что до рекурсия-итерация: да, в общем случае рекурсия медленнее (не в смысле сложности алгоритма!) из-за вызова функции, но эта разница не так уж велика, а оптимизатором часто просто убирается вовсе.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.