Наилучший случай
Наилучшим случаем для алгоритма является такой набор данных, на котором алгоритм выполняется за минимальное время. Такой набор данных представляет собой комбинацию значений, на которой алгоритм выполняет меньше всего действий.
Вообще, время выполнения алгоритма в наилучшем случае очень часто оказывается маленьким или просто постоянным, поэтому мы будем редко проводить подобный анализ.
Пример: Если мы исследуем алгоритм поиска, то набор данных является наилучшим, если искомое значение (целевое значение) записано в первой проверяемой алгоритмом ячейке. Такому алгоритму, вне зависимости от его сложности, потребуется одно сравнение. Заметим, что при поиске в списке, каким бы он сложным ни был, наилучший случай требует постоянного времени.
Пример: Если мы исследуем алгоритм поиска, то набор данных является наилучшим, если искомое значение (целевое значение) записано в первой проверяемой алгоритмом ячейке. Такому алгоритму, вне зависимости от его сложности, потребуется одно сравнение. Заметим, что при поиске в списке, каким бы он сложным ни был, наилучший случай требует постоянного времени.
Наихудший случай
Анализ наихудшего случая чрезвычайно важен, поскольку он говорит о максимальном времени работы алгоритма. При анализе наихудшего случая необходимо найти входные данные, на которых алгоритм будет выполнять больше всего работы.
Анализ наихудшего случая дает верхние оценки для времени работы частей нашей программы в зависимости от выбранных алгоритмов.
Пример: Для алгоритма поиска подобные входные данные - это список, в котором целевое значение окажется последним из рассматриваемых или вообще отсутствует. В результате может потребоваться N сравнений.
Анализ наихудшего случая дает верхние оценки для времени работы частей нашей программы в зависимости от выбранных алгоритмов.
Пример: Для алгоритма поиска подобные входные данные - это список, в котором целевое значение окажется последним из рассматриваемых или вообще отсутствует. В результате может потребоваться N сравнений.
Средний случай
- В основе анализа среднего случая лежит определение различных групп, на которые следует разбить возможные входные наборы данных. Время работы алгоритма на всех входных данных одной группы должно быть одинаковым, в противном случае группу следует разбить еще раз.
- На втором шаге определяется вероятность, с которой входной входной набор данных принадлежит каждой группе.
- На третьем шаге подсчитывается время работы алгоритма на данных из каждой группы.
Среднее время работы вычисляет по формуле
 |
| Несоответствие левой и правой частей формулы (левая зависит от n, а правая нет) является кажущимся: и разбиение на группы, и значение параметров pi и ti в правой части тоже зависят от n. |
, где через n обозначен размер входных данных, через m число групп, через pi - вероятность того, что входные данные принадлежат группе с номером i, а через ti - время, необходимое алгоритму для обработки данных из группы с номером i.
В некоторых случаях мы будем предполагать, что вероятности попадания входных данных в каждую из групп одинаковы. Например, если групп пять, то вероятность попасть в первую группу такая же, как вероятность попасть во вторую, и т.д., то есть вероятность попасть в каждую группу равна 0,2. В этом случае среднее время работы можно либо оценить по предыдущей формуле, либо воспользоваться эквивалентной ей упрощенной формулой
, справедливой при равной вероятности всех групп.
В некоторых случаях мы будем предполагать, что вероятности попадания входных данных в каждую из групп одинаковы. Например, если групп пять, то вероятность попасть в первую группу такая же, как вероятность попасть во вторую, и т.д., то есть вероятность попасть в каждую группу равна 0,2. В этом случае среднее время работы можно либо оценить по предыдущей формуле, либо воспользоваться эквивалентной ей упрощенной формулой
, справедливой при равной вероятности всех групп.
