Оценка для метода полного перебора.
Данный метод начинается
с построения множества всех решений данной задачи. Для этого не-
обходимо извлечь из базы данных все функции, на что требуется
np
элементарных операций.
На каждом шаге алгоритма необходимо вычислить целевую функ-
цию для полного решения. Для каждой комбинации функций (для
каждого решения) необходимо отобрать
nq
исходных кодов. Для ис-
ключения дубликатов необходимо провести их поиск, последовательно
сравнивая исходные коды. Это добавляет
qn
−
1
i
=1
i
=
(
qn
−
1)
qn
2
элемен-
тарных операций.
Однако наибольший вклад в оценку дает число повторений алго-
ритма. Для перебора всех возможных решений понадобится
p
n
повто-
рений. Получаем окончательную оценку для метода:
ϕ
полн
(
n
) =
pn
+
p
n
qn
+
qn
(
qn
−
1)
2
.
Оценка для метода случайного поиска.
Оценка для данного ме-
тода будет во многом зависеть от того, какое число шагов будет вы-
брано. При малом числе шагов оценка получится небольшой, однако
большой точности можно достичь только при сравнительно большом
числе повторений алгоритма.
Для построения случайных решений необходимо выбрать все
функции. Для этого требуется
np
элементарных операций. Для ка-
ждого случайно выбранного решения требуется вычислить целевую
функцию. Целевая функция вычисляется для полного решения, такие
затраты также были уже вычислены (метод полного перебора), они
равны
qn
+
qn
(
qn
−
1)
2
. В итоге оценка будет иметь следующий вид:
ϕ
случ
(
n
) =
k pn
+
qn
+
qn
(
qn
−
1)
2
,
где
k
— число повторений алгоритма.
Оценка для метода динамического программирования.
Данный
метод имеет вполне конкретное число проходов. Для каждого требо-
вания необходимо отыскать все функции и выбрать ту, для которой
целевая функция, вычисленная по частичному решению, дает наилуч-
ший результат.
Число проходов алгоритма будет определяться произведением чи-
сла требований на среднее число функций, приходящихся на требова-
ние, т.е.
np
.
Затраты на вычисление целевой функции будут увеличиваться от
шага к шагу. Их можно вычислить по сумме ряда
n
i
=1
pqi
=
pq
n
(
n
+ 1)
2
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 3 29
