Различные алгоритмы, разработанные для решения одной и той же задачи, часто очень сильно отличаются по эффективности. Эти различия могут быть намного значительнее тех, которые вызваны применением неодинакового аппаратного и программного обеспечения. Проявляются они прежде всего в плане расходов времени.
В общем случае время работы алгоритма увеличивается с увеличением количества входных данных, поэтому общепринятая практика — представлять время работы как функцию, зависящую от количества входных элементов.
Наиболее адекватное понятие размера входных данных зависит от рассматриваемой задачи. Во многих задачах, таких как сортировка или дискретные преобразования Фурье, это количество входных элементов, например, размер n сортируемого массива. Для многих других задач, таких как перемножение двух целых чисел, наиболее подходящая мера размера ввода — количество битов, необходимых для представления входных данных в двоичных обозначениях.
Время работы алгоритма для тех или иных входных данных измеряется в количестве элементарных операций, или шагов, которые необходимо выполнить. Можно исходить из точки зрения, согласно которой для выполнения каждого шага требуется фиксированное время, тогда время работы алгоритма — это сумма промежутков времени, необходимых для выполнения каждой входящей в его состав выполняемой инструкции.
Необходимо заметить, что даже если размер входных данных является фиксированной величиной, время работы алгоритма может зависеть от самих входных данных. В примере сортировки массива время зависит от степени упорядоченности сортируемых величин, которой они обладали до ввода. Очевидно, что самый благоприятный случай — это когда все элементы массива уже отсортированы, а наихудший — когда массив находится в порядке, обратном требуемому. Далее основное внимание будет уделено времени работы в наихудшем случае, т. е. максимальному времени работы для любых входных данных размером n. На то есть три причины:
- 1. Время работы алгоритма в наихудшем случае — это верхний предел этой величины для любых входных данных.
- 2. В некоторых алгоритмах наихудший случай встречается довольно часто.
- 3. Характер поведения усредненного времени ничем не лучше поведения работы для наихудшего случая.
