39
правок
Изменения
Нет описания правки
Для вышеописанных массивов <tex> A, B </tex> алгоритм выглядит следующим образом:
Первые 7 итераций сравниваются числа <tex>1, 2, 3, 4, 5, 6, 7</tex> из массива <tex>A</tex> с числом <tex>20000</tex>, так как <tex>20000</tex> больше, то элементы массива <tex>A</tex> копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим '''«галопа»''': сравнивает с числом <tex>20000</tex> последовательно элементы <tex>8, 10, 14, 22, 38, 7+2^{i - 1}, ..., 10000 </tex> массива <tex>A</tex>. (<tex> \thicksim\log_{2}(n)</tex> сравнений). После того как конец массива <tex>A</tex> достигнут и известно, что он весь меньше <tex>B</tex>, нужные данные из массива <tex>A</tex> копируются в результирующий.
== Доказательство времени работы алгоритма ==
Для оценки времени работы алгоритма '''Timsort''' составим рекуррентное соотношение. Пусть <tex> T(n) </tex> — время сортировки массива длины n. Рассмотрим последнее слияние двух подмассивов <tex> run1 </tex> и <tex> run2 </tex>:
<tex> T(n) = T(run1.size) + T(run2.size) + O(run1.size + run2.size) </tex>. Алгоритм построен таким образом, что сливаемые подмассивы имеют примерно равные размеры. Таким образом можно считать:
<tex> T(n) = T(run1.size) + T(run2.size) + O(run1.size + run2.size) </tex> <tex> \approx 2T(n/2) + O(n) \approx </tex> <tex> 4T(n/4) + 2O(n) \approx \dots \approx 2^{k}T(1) + kO(n) </tex>.
Осталось оценить <tex>k</tex>. <tex>n/minrun</tex> - количество сливаемых блоков, откуда следует, что <tex>2^{k} = n/minrun</tex>, значит <tex> k = log(n/minrun)</tex>.
<tex>T(n) \approx 2^{k}T(1) + kO(n) </tex> = <tex> log(n/minrun) + </tex><tex>log(n/minrun)O(n)</tex> <tex> = O(nlog(n)). </tex>
== Источники ==
