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

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

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

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

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

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

2.8. Вопросы, системы и концептуальные случаи

Из книги автора

2.8. Вопросы, системы и концептуальные случаи «Вопросы являются следствием определенных точек зрения, они проистекают из чего-то такого, что помогает выяснять неясные моменты, формулировать ответы и уточнять проблематичные вещи. Не следует думать, что наши взгляды на


Средний тип систем

Из книги автора

Средний тип систем Сложнее всего решать вопросы производительности именно в системах среднего типа (от 10 до 50 телефонов). Как правило, такие системы развертываются только на одном или двух серверах и, таким образом, каждая машина должна будет обрабатывать по несколько


Средний уровень

Из книги автора

Средний уровень Системы веб-аналитики предлагают три уровня анализа: базовый, средний и продвинутый. Эти уровни зависят от знаний клиента и от того, какое воздействие на эффективность сайта будут иметь результаты анализа. Давайте рассмотрим эти уровни на примере


4. Апселл во время заказа № 2 – средний

Из книги автора

4. Апселл во время заказа № 2 – средний Второй апселл (если человек согласился на первый) можно предложить стоимостью 100 %. Тренинг стоит $100, первый апселл – 50, второй – 100. Это логично. Если человек решил потратить 150 долларов, то, когда ему предлагают потратить еще 100, он


14. Лучший способ

Из книги автора

14. Лучший способ Очень хорошая тема для статьи, аудио или видео: «Лучший способ сбросить лишние килограммы», «Лучший способ раскрутить свою группу “ВКонтакте”», «Лучший способ сделать то-то и то-то». Люди обожают узнавать, как лучше сделать, нам нравится лучший способ


Средний чек

Из книги автора

Средний чек Первый, наиболее дешевый и простой способ поднять объемы продаж – тщательная работа со средним чеком. Увеличить его можно различными способами, один из самых быстрых – предлагать клиентам, уже совершившим покупку, приобрести что-то еще.Как правильно это


«Магнит сверху», поднимающий средний чек

Из книги автора

«Магнит сверху», поднимающий средний чек В интернет-магазинах можно хорошо простимулировать увеличение средней суммы покупки за счет использования денежных планок, при «пробитии» которых покупатель будет получать дополнительную скидку.Например, при покупке на сумму


4.3. Общие случаи использования отсечения

Из книги автора

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


Самый лучший IQ-тест

Из книги автора

Самый лучший IQ-тест Весь мир куда-то глобализуется, и мы должны глобализоваться туда же, и отклонение хотя бы в деталях (и даже скорее в деталях и форме, чем в содержании) воспринимается как опасное вольнодумство; напротив, точное соблюдение подробностей крайне


ГЛАВА 01 МАЛЫЙ И СРЕДНИЙ БИЗНЕС В РОССИИ

Из книги автора

ГЛАВА 01 МАЛЫЙ И СРЕДНИЙ БИЗНЕС В РОССИИ «Существует салонная игра, — продолжал Дюпен, — в которую играют с помощью географической карты. Один играющий предлагает другому найти задуманное слово — название города, реки, государства или империи — среди массы надписей,


Случаи потери информации и принципы восстановления

Из книги автора

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


Отдельные случаи восстановления

Из книги автора

Отдельные случаи восстановления Ранее был рассмотрен долгий путь восстановления данных из RAID-массива: подключение дисков к обычному контроллеру по-одному, создание их образов, сборка виртуального массива и извлечение из него файлов. Это универсальная, наиболее


Случаи, когда инструментальных средств недостаточно

Из книги автора

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


Телефон на все случаи жизни [121]

Из книги автора

Телефон на все случаи жизни [121] Для того чтобы компания эффективно работала, необходимо сокращать затраты на управление и на предоставляемые услуги. При этом качество услуг должно повышаться, а их спектр – расширяться. Эти противоречивые требования не возможно