6 / 13
К.А. Кивва, И.В. Рудаков
38
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
С учетом формул (1), (5), после раскрытия произведения
1
1
t j
i
i
k
− −
=
∏
наиболее
быстро растущим членом получившегося полинома оказывается:
( )
(
)(
)
(
)(
) (
)(
)(
)
− − + + +
− + −
− −
− + − −
=
=
∏
1 2 4
1
1
6
1
1
.
j t t j
j
t
j t t
t j
t i
t j i
t
i
pq
s
При этом в произведении
1
1
t
i
i
k
−
=
∏
(6) наиболее быстро растущим членом по-
линома аналогично является
(
)
2
1/3 1
.
t
s
−
(7)
Тогда наиболее быстро растущим членом полинома (6) для
t
> 1 будет или
(
)
2
1/3 1
,
t
s
−
или
(
)(
) (
)(
)(
)
(
)
(
)
3 2
2
3
1 2 4
1
1
6
3
3 3 8 2 2 6
6
1
.
j t t j
j
t
j t t
j
j
j t
t
t
t
t
t
t j
s s
s
d
− − + + +
− + −
+ − + − + − +
− −
=
(8)
В рамках рассматриваемой задачи
j
является целым числом. Однако для
определения промежутков монотонности выражения (8) удобно рассмотреть
его как функцию от вещественного аргумента
j
, после чего для определения
конкретных значений выражения (8), которые могут быть получены при реше-
нии задач локализации объекта на изображении, брать только целые значения
j
.
Взяв частную производную от функции (8) по
j
, с учетом области допусти-
мых значений
j
согласно условию задачи и формуле (6), нетрудно убедиться в
том, что функция (8) от
j
в области допустимых значений
j
монотонно убывает.
В этом случае на рассматриваемом промежутке значений
j
функция (8)
имеет наибольшее значение при наименее возможном
j
, т. е. при
j
= 1:
(
)
(
)
2
3 2
2
3
1
18
1
2 3
5
3
3 3 8 2 2 6
6
6
1
.
t
t
j
j j t
t
t
t
t
t
j
s
s
− + −
+ − + − + − +
=
=
(9)
Видно, что значения выражения (7) больше, чем значения выражения (9),
на всем промежутке допустимых значений
t
.
Подводя итог, можно заключить, что самым быстро растущим членом по-
линома (6) при
t
> 1 является
(
)
2
1/3 1
.
t
s
−
Таким образом, сложность
T
(
s
) рассматриваемого рекурсивного алгоритма
разбиения изображения на подокна в худшем случае имеет порядок