Алгоритмы сортировки: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
Нет описания правки |
||
Строка 80:
Поскольку время работы алгоритма зависит от того, на каком языке программирования был написан код, как он был скомпилирован, на каком компьютере выполняется и т. д., то мы будем считать не время работы алгоритма, а ''количество операций'', выполняемых алгоритмом. Наш алгоритм ''N''-1 раз выполняет поиск минимума - в первый раз минимум ищется среди ''N'' элементов, и на это тербуется порядка N операций, второй раз - среди ''N''-1 элемента, и т. д. Таким образом, на посик минимума всего потребуется N + (N-1) + ... + 3 + 2 = (N+2)(N-1)/2 опреаций, что примерно равно N<sup>2</sup>/2 операций. На перестановку минимумов на свои места требуется порядка N операций. При больших N N<sup>2</sup>/2 много больше N, поэтому операциями перестановки максимума можно пренебречь, и сказать, что наш алгоритм работает за время порядка N<sup>2</sup>/2, где N - количество чисел. Алгоритмы, которые требуют порядка CN<sup>2</sup>/2 операций (где С - некоторая константа, не зависящая от N), называют ''квадратичными''. Посмотрим, как растет величина N<sup>2</sup> с ростом N:
N 10 1,000 10,000 1,000,000
N<sup>2</sup> 100 1,000,000 100,000,000 1,000,000,000,000
Видно, что уже при N равном миллиону количество операций достигает триллиона!
Теперь посмотрим, как используется память. Мы не используем никакой дополнительной памяти, кроме той, в которую записан исходный массив. Казалось бы, меньше памяти использовать нельзя! Это не совсем точное утверждение, но пока мы оставим его в таком виде, и вернемся к этому вопросу позже.
| |||