осуществляется логарифмирование, обозначим через
r
. Поскольку количе-
ство простых чисел в факторной базе можно считать равным
h
=
M
ln
M
, то
общее число элементов во всех
h
dim-мерных матрицах будет равно
N
=
h
(ln
r
+ 1)
dim
=
M
ln
M
(ln
r
+ 1)
dim
.
Число всевозможных пар элементов в матрицах равно
N
2
/
2
. Для просто-
ты считаем, что все элементы в матрицах различны, к случаю совпадения
чисел и наличия линейных зависимостей мы вернемся позднее. Поскольку
необходимо составить
h
+ 1
уравнение, необходимо столько же совпадений
после четвертого этапа. Чтобы попасть в одну совпадающую пару, число
всевозможных пар элементов должно быть
1
/P
. Чтобы попасть в
h
+
+ 1
совпадающую пару, число всевозможных пар должно быть не меньше
(
h
+ 1)
/P
. Поэтому
N
2
2
>
h
+ 1
P
;
→
M
ln
M
2
(ln
r
+ 1)
2dim
>
2
M
ln
M
(
P
0
)
2
(1 +
C
)
;
M
ln
M
(ln
r
)
2dim
>
2
(1 +
C
)
ln
n
ln
M
2
ln
n
ln
M
.
(14)
Оценим
M
в стандартных обозначениях субэкспоненциальной сложно-
сти:
M
= exp
C
0
(ln
n
)
q
(ln ln
n
)
1
−
q
,
0
< q <
1
, C
0
— константа.
Тогда неравенство (14) запишется следующим образом:
exp
C
0
(ln
n
)
q
(ln ln
n
)
1
−
q
+ 2dim
∙
ln ln
r
−
ln ln
M >
>
exp
2 ln
n
ln
M
∙
ln
ln
n
ln
M
;
C
0
→
(ln
n
)
q
(ln ln
n
)
1
−
q
+ 2dim
∙
ln ln
r
−
−
q
ln ln
n >
2 ln
n
C
0
(ln
n
)
q
(ln ln
n
)
1
−
q
(ln ln
n
−
q
ln ln
n
) ;
→
C
0
(ln
n
)
q
(ln ln
n
)
1
−
q
+ 2dim
∙
ln ln
r
−
q
ln ln
n >
>
2 (1
−
q
)
C
0
(ln
n
)
1
−
q
(ln ln
n
)
q
.
(15)
Очевидно, что минимальное
q
, при котором выполняется неравенство
(15), это
q
= 1
/
2
.
Самая трудоемкая часть алгоритма — это этап 4, поскольку каждый эле-
мент из матриц будет последовательно делиться на числа из факторной базы.
Поэтому итоговая сложность алгоритма оценивается как
S
≈
O
(
hN
) =
O
M
ln
M
2
(ln
r
+ 1)
dim
!
=
=
O
(exp (2 (ln
M
−
ln ln
M
) + dim
∙
ln ln
r
)) =
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2 91
