=
O
exp 2
C
0
(ln
n
)
q
(ln ln
n
)
1
−
q
−
q
ln ln
n
+ dim ln ln
r
=
=
O
exp 2
C
0
(ln
n
)
q
(ln ln
n
)
1
−
q
+ dim ln ln
r
−
2
q
ln ln
n .
(16)
Теперь главный вопрос заключается в том, что нельзя ли за счет
dim
подобрать как можно меньший коэффициент
C
0
так, чтобы выполнялось
неравенство (15). Пусть
dim =
C
00
(ln
n
)
q
. Тогда неравенство (15) запишется
как
C
0
+ 2
C
00
ln ln
r
(ln ln
n
)
1
−
q
(ln
n
)
q
(ln ln
n
)
1
−
q
−
q
ln ln
n >
>
2 (1
−
q
)
C
0
(ln
n
)
1
−
q
(ln ln
n
)
q
;
→
C
0
+ 2
C
00
ln ln
r
(ln ln
n
)
1
−
q
>
2 (1
−
q
)
C
0
.
Второе условие на коэффициенты вытекает из минимальности коэффи-
циента при
(ln
n
)
q
(ln ln
n
)
1
−
q
в выражении (16):
S
=
O
exp 2
C
0
+
C
00
ln ln
r
(ln ln
n
)
1
−
q
×
×
(ln
n
)
q
(ln ln
n
)
1
−
q
−
2
q
ln ln
n .
Таким образом, получаем соотношения на коэффициенты
C
0
+ 2
C
00
ln ln
r
(ln ln
n
)
1
−
q
>
2 (1
−
q
)
C
0
;
min
C
0
,C
00
2
C
0
+
C
00
ln ln
r
(ln ln
n
)
1
−
q
=
C.
При
q
= 1
/
2
минимум
C
=
√
3
≈
1
,
73
достигается при
C
0
= 1
/
√
3
и соот-
ветственно
C
00
=
1
√
3
(ln ln
n
)
1
−
q
ln ln
r
. Таким образом, сложность оптимального
варианта алгоритма
S
=
O
exp
√
3
√
ln
n
∙
ln ln
n
−
ln ln
n
=
L
n
h
1
/
2
,
√
3
i
.
Соответствующие параметры алгоритма следующие:
M
= exp
r
ln
n
∙
ln ln
n
3
!
,
dim =
r
1
3
ln
n
∙
ln ln
n
ln ln
r
,
где
M
— ограничение факторной базы,
dim
— размер матриц в алгоритме.
При этом объем необходимой памяти при наименьшей вычислительной
сложности составляет
92 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2
