 |
|
����� � �������, ��������, �������������������: ������������ ������������� ���������.
������� ������.
������� ������ � ������ ��������� ����� ������� ������������� ��������� ��� ��������� ������ y ����� ���� ������� �� ������� ���������� M ����������� n * n. �������� ���� ������� ������������ ��������� �������:
����� ������� ����������� ������������ ������� ���������. ������� ���� ��������� ������ �������� ��� ��� ��� ��� ���. ��������� �� ������� �1�, �� ����������� �������, ������������ ���������� � ������ y, ���-�� � ����� ������ ������������ ������������� ���������. ��� ������ ������� ���������� ��� ������ PABCQRABCSABTU
|
|
j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
i |
|
P |
A |
B |
C |
Q |
R |
A |
B |
C |
S |
A |
B |
T |
U |
|
1 |
P |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
A |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
3 |
B |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
4 |
C |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
5 |
Q |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
6 |
R |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
7 |
A |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
8 |
B |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
9 |
C |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
10 |
S |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
11 |
A |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
12 |
B |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
13 |
T |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
14 |
U |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
�� ����������� ���� ������� ����� ������, ��� ������������� �������������� ����������� � ������ ������� �������� ABC, � ����������� y(2, 4) � y(7, 9), � AB, � ����������� y(2, 3), y(7, 8) � y(11, 12). ����� ������� ����� ������� �� ���, � ������, ABC.
��� ��� �����������, ��������� ������� �����������, ���������� ��������� �������� ��� ������� ����������, M(1...n-1,i+1...n), �� ���� ����� n(n-1)/2 ���������. ����� �������, ���������� ������� ������� �������, ����������������� O(n2).
����� �� ��������, � ���������� � ���������.