74
правки
Изменения
м
→Алгоритм «разделяй и властвуй»
Получили асимптотическое уравнение <tex> T(n) = T\left( \dfrac{n}{2}\right) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>.
Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением <tex>\$</tex> в конец). На шаге слияния мы сможем избавиться от него.
* '''База рекурсии'''
