Книга: Фундаментальные алгоритмы и структуры данных в Delphi

Лучший, средний и худший случаи

Лучший, средний и худший случаи

Помимо всего прочего, необходимо рассмотреть еще один вопрос. О-нотация относится к среднему случаю. Вернемся к нашим экспериментам, связанным с поиском элемента в массиве. Если бы фамилия "Smith" всегда была первым элементом в массиве, последовательный поиск был бы быстрее бинарного, - искомый элемент был бы обнаружен при первом же выполнении цикла. Такая ситуация известна под названием лучший случай. Для нашего примера в О-нотации ее можно представить как O(1) (т.е. выполнение алгоритма занимает одно и то же время независимо от количества элементов в массиве).

Если бы фамилия "Smith" всегда была последним элементом в массиве, последовательный поиск был бы очень медленным. Такая ситуация известна под названием худший случай. В нашем примере ее можно представить как О(n), точно так же, как и для среднего случая.

Несмотря на то что для бинарного поиска быстродействие в лучшем случае (искомый элемент всегда находится в средине массива) равно быстродействию в лучшем случае для последовательного поиска, тем не менее, его быстродействие в худшем случае намного выше. Собранные нами статистические данные при поиске элемента, которого нет в массиве, являются значениями для худшего случая.

В общем, при выборе алгоритма следует учитывать значения в О-нотации для среднего и худшего случаев. Лучшие случаи, как правило, не интересны, поскольку программисты всегда более обеспокоены "граничными" условиями, по которым и будут судить о быстродействии приложения.

Таким образом, мы увидели, что О-нотация - очень ценное средство оценки быстродействия различных алгоритмов. Кроме того, следует помнить, что О-нотация в общем случае имеет смысл только для больших n. Для небольших n выбор алгоритма лучше осуществлять на основе статистических данных о времени его выполнения. Единственным достоверным методом оценки эффективности алгоритма является определение времени его работы. Поэтому не гадайте, а интенсивно используйте профилировщик.

Оглавление книги