 |
|
������.
������ ������� ����������. C����� O().
��� ������ ������������������ ���������� ����� ������������ ������ �������. ����� ������������� - ������ ��������� ������ �������� �� ���������� ������� � �������� ����� ����������. ������ ������ - ������� ����� ����������. ��������, �� ����� ����������, ��� ����� ������ ���� O(n) (�������� ���: � ������� �� n).����� ���������� ����������� O(), ����� � ���� �� ������ ����� ����������, � ������ ��� ������ ������, ������ � ��������� �� ����������� ���������. ����� �������, ��������, ��� ��������� ��������� ����� ������� O(n2), ����� � ����, ��� ����� ���������� ������ ������ �� �������, ��� ������� ���������� ���������. ����� �������������, ��� ��� �����, ���������� �� �������, ��� ��������� �����, �������������� �������� ����� ��� ���������� ������ �������.
n |
n2 |
||
| 1 | 0 | 0 | 1 |
| 16 | 4 | 64 | 256 |
| 256 | 8 | 2,048 | 65,536 |
| 4,096 | 12 | 49,152 | 16,777,216 |
| 65,536 | 16 | 1,048,565 | 4,294,967,296 |
| 1,048,476 | 20 | 20,969,520 | 1,099,301,922,576 |
| 16,775,616 | 24 | 402,614,784 | 281,421,292,179,456 |
���� �������, ��� ����� � ������� ������������� �������������, �� ��� ������ � 1048476 ���������� ��������� � �������� ������ O(log n) ����������� 20 �����������, � ��������� � �������� ������ O( n2 ) - ����� 12 ����.
���� ��� ���������, ��������, O ( n*log n ), �� ��� ������ �� ������, ��� ��� ��������� ����������.������ � �� ��������� ���������, �� ���� ������ ����� ����, ������ � 1000 ��� �����������. O() ������ ���� ��, ��� �� ����� ���������� �������������� ��� ������� n*log n.
�� ������� ������� ���������� ��������, ������������ ������� �����.�� ����, ���� � ��������� ���� ������� ����������� O(n) ��� - ��������, ���������, � �������� - O(n2) ���, �� ����� ��������� ��������� - O(n2), ��� ��� � ����� ������ ��� ���������� n ����� ������� ( � ������������, ����������� ����� ��� ) �������� ������ ���������� ��������� �����, ��� ����� ������ �� �������������� ���� ������, ������ ���������, �� ������ ���������. O() ���������� ������������� ����������� !
��������� ��������� �� �������.������� ����� ������ ������. ����� � ��� ���� O( log2n). �� log2n=log3n/log32, � log32, ��� � ����� ���������, ����������� - ������ �() �� ���������. ����� �������, O( log2n) = O( log3n).
� ������ ��������� �� ����� ������� ����������, �, ������, � ������ ��� �� ����� ������.
����� �� ��������, � ���������� � ���������.