А.Ф. Деон, Ю.И. Терентьев
8
этапе выполняется внешний цикл по правой неупорядоченной части
массива. В заголовоке цикла
for
(
int j =
1
; j < n; j++
) выполняется
одна операция на начальную установку индекса
int j = 1
и одна — на
предварительную проверку условия
j < n
:
1,1
1 1 2
W
= + =
.
Кроме того, на каждой итерации внешнего цикла в заголовке вы-
полняется одна операция на очередную проверку окончания цикла
j < n
и две операции на увеличение переменной
j++
:
(
)
(
)
1
1,2
1
1 2 3 1
n
j
W
n
−
=
= + = −
∑
.
Всего на первом этапе дихотомической вставки выполняется сле-
дующее количество операций:
(
)
1
2,1
2,2
2 3 1 3 1
W W W
n
n
= + = + − = −
.
По аналогии с методом последовательной вставки на втором эта-
пе
if
(
a
[
j –
1]
<= a
[
j
])
continue
выполняется следующее количество
операций:
(
)
1
2
1
4 4 1
n
j
W
n
−
=
= = −
∑
.
На третьем этапе с помощью инструкции
int i = DichPos
(
a, j, a
[
j
])
определяется место вставки. Поскольку общее минимальное количе-
ство блокирует второй этап, то интерес представляет только макси-
мальное количество операций:
(
)
(
) (
)
(
)
1
1
3
max
2
2
1
1
1
1 3 9]log [
4 9]log [
1
n
n
DichPos
j
j
W W
n
n n
−
−
=
=
= +
= + +
= +
−
∑
∑
.
На четвертом этапе выполняется вставка, рассмотренная ранее в
сортировке методом последовательной вставки. В инструкции
int
r = a
[
j
] запоминается вставляемое значение, затрачивая следующее
количество операций:
(
)
1
4,1
1
2 2 1
n
j
W
n
−
=
= = −
∑
.
Далее проводится сдвиг упорядоченной части массива в
инструкции
for
(
int m = j; m > i; m– –
)
a
[
m
]
= a
[
m –
1]. Перед
итерациями цикла произойдет одна операция на установку индекса
int m = j
и одна операция
m > i
на проверку необходимости
