3622
правки
Изменения
м
→Доказательство времени работы алгоритма
Пусть <tex>k</tex> {{---}} число кусков, на которые разбился наш исходный массив, очевидно <tex> k </tex> = <tex dpi=150> \left\lceil \frac{n}{minrun} \right\rceil </tex>.
Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>O(n \log{n})</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длину. Можно сказать больше: пока <tex>k > 3</tex> сливаемые подмассивы будут именно одинаковой длинны длины (данный факт хорошо виден на примере). Безусловно, после разбиения массива на блоки длиной <tex>minrun</tex> последний блок может быть отличен от данного значения, но число элементов в нём не превосходит константы <tex> minrun </tex>.
Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается в <tex>\approx 2</tex> раза. Таким образом получаем, что каждый подмассив <tex>run_i</tex> может участвовать в не более <tex>O(\log{n})</tex> операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex>O(\log{n})</tex> раз. Элементов <tex>n</tex>, откуда получаем оценку в <tex>O(n\log{n})</tex>.
