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