 | Эта статья требует дополнительных ссылок для проверки . ( март 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В информатике , лучший , худший, и средние случаи данного алгоритма выразить то , что ресурс использования является , по крайней мере , в большинстве и в среднем , соответственно. Обычно рассматриваемый ресурс - это время выполнения, то есть временная сложность , но также может быть память или другой ресурс. Лучшим случаем является функция, которая выполняет минимальное количество шагов над входными данными из n элементов. Наихудший случай - это функция, которая выполняет максимальное количество шагов для входных данных размера n. Средний случай - это функция, которая выполняет среднее количество шагов над входными данными из n элементов.
В вычислениях в реальном времени время выполнения в наихудшем случае часто вызывает особую озабоченность, поскольку важно знать, сколько времени может потребоваться в худшем случае, чтобы гарантировать, что алгоритм всегда завершится вовремя.
При анализе алгоритмов чаще всего используются средняя производительность и производительность в наихудшем случае . Менее широко используется производительность в лучшем случае , но у нее есть применение: например, когда известны лучшие варианты отдельных задач, их можно использовать для повышения точности общего анализа наихудшего случая. Ученые-информатики используют методы вероятностного анализа , особенно ожидаемого значения , для определения ожидаемого времени работы.
Термины используются в других контекстах; например, наихудший и лучший результат запланированной эпидемии, наихудшая температура, воздействию которой подвергается элемент электронной схемы, и т. д. Если используются компоненты с заданным допуском , устройства должны быть спроектированы для правильной работы с наихудшими - случайное сочетание допусков и внешних условий.
Лучшая производительность для алгоритма [ править ]
Термин « наилучшая производительность» используется в информатике для описания поведения алгоритма в оптимальных условиях. Например, лучший случай для простого линейного поиска по списку происходит, когда желаемый элемент является первым элементом списка.
Разработка и выбор алгоритмов редко основываются на производительности в лучшем случае: большинство академических и коммерческих предприятий больше заинтересованы в улучшении средней сложности и производительности в наихудшем случае . Алгоритмы также можно тривиально модифицировать, чтобы обеспечить хорошее время работы в лучшем случае, путем жесткого кодирования решений для конечного набора входных данных, что делает измерение почти бессмысленным. [1]
Эффективность в худшем и среднем случае [ править ]
| В этом разделе не процитировать любые источники . ( Сентябрь 2017 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Анализ производительности наихудшего случая и анализ производительности среднего случая имеют некоторое сходство, но на практике обычно требуют разных инструментов и подходов.
Определить, что означает типичный ввод, сложно, и часто этот средний ввод имеет свойства, которые затрудняют математическую характеристику (рассмотрим, например, алгоритмы, которые предназначены для работы со строками текста). Точно так же, даже когда разумное описание конкретного «среднего случая» (которое, вероятно, будет применимо только для некоторых применений алгоритма) возможно, они, как правило, приводят к более сложному анализу уравнений. [2]
Анализ наихудшего случая дает надежный анализ (наихудший случай никогда нельзя недооценивать), но такой анализ может быть излишне пессимистичным , поскольку может не быть (реалистичных) исходных данных, которые потребовали бы такого количества шагов.
В некоторых ситуациях может потребоваться пессимистический анализ, чтобы гарантировать безопасность. Однако часто пессимистический анализ может быть слишком пессимистичным, поэтому анализ, который приближается к реальному значению, но может быть оптимистичным (возможно, с известной низкой вероятностью отказа), может быть гораздо более практичным подходом. Один из современных подходов в академической теории к преодолению разрыва между анализом наихудшего и среднего случая называется сглаженным анализом .
При анализе алгоритмов, выполнение которых часто занимает мало времени, но периодически требует гораздо большего времени, можно использовать амортизированный анализ для определения наихудшего времени выполнения (возможно, бесконечного) ряда операций . Эта амортизированная стоимость наихудшего случая может быть намного ближе к средней стоимости случая, при этом обеспечивая гарантированный верхний предел времени работы.
Анализ наихудшего случая связан со сложностью наихудшего случая . [3]
Практические последствия [ править ]
Многие алгоритмы с плохой производительностью в наихудшем случае имеют хорошую производительность в среднем случае. Для проблем, которые мы хотим решить, это хорошо: мы можем надеяться, что конкретные экземпляры, которые нам интересны, являются средними. Для криптографии это очень плохо: мы хотим, чтобы типичные примеры криптографической проблемы были сложными. Здесь для некоторых конкретных задач можно использовать такие методы, как случайная самовосстановление, чтобы показать, что худший случай не сложнее среднего или, что то же самое, что средний случай не легче худшего.
С другой стороны, некоторые структуры данных, такие как хеш-таблицы, имеют очень плохое поведение наихудшего случая, но хорошо написанная хеш-таблица достаточного размера статистически никогда не даст наихудшего случая; среднее количество выполняемых операций следует экспоненциальной кривой спада, поэтому время выполнения операции статистически ограничено.
Примеры [ править ]
Алгоритмы сортировки [ править ]
| Алгоритм | Структура данных | Сложность по времени: Лучшая | Временная сложность: Средняя | Временная сложность: худшая | Сложность космоса: Худшая |
|---|---|---|---|---|---|
| Быстрая сортировка | Множество | O ( п журнал ( п )) | O ( п журнал ( п )) | О ( п 2 ) | О ( п ) |
| Сортировка слиянием | Множество | O ( п журнал ( п )) | O ( п журнал ( п )) | O ( п журнал ( п )) | О ( п ) |
| Сортировка в куче | Множество | O ( п журнал ( п )) | O ( п журнал ( п )) | O ( п журнал ( п )) | О (1) |
| Гладкая сортировка | Множество | О ( п ) | O ( п журнал ( п )) | O ( п журнал ( п )) | О (1) |
| Пузырьковая сортировка | Множество | О ( п ) | О ( п 2 ) | О ( п 2 ) | О (1) |
| Вставка сортировки | Множество | О ( п ) | О ( п 2 ) | О ( п 2 ) | О (1) |
| Выборочная сортировка | Множество | О ( п 2 ) | О ( п 2 ) | О ( п 2 ) | О (1) |
| Бого сортировка | Множество | О ( п ) | О ( п п !) | O (∞) | О (1) |
- Сортировка вставкой, примененная к списку из n элементов, предполагается, что все они разные и изначально расположены в случайном порядке. В среднем половина элементов в списке A 1 ... A j меньше, чем элемент A j +1 , а половина - больше. Следовательно, алгоритм сравнивает ( j + 1) -й элемент, который должен быть вставлен в среднем, с половиной уже отсортированного подсписка, так что t j = j / 2. Вычисление результирующего времени выполнения в среднем случае дает квадратичную функцию от размера входных данных, как и время выполнения в наихудшем случае.
- Быстрая сортировка применяется к списку из n элементов, опять же предполагается, что все они разные и изначально расположены в случайном порядке. Этот популярный алгоритм сортировки имеет среднюю производительность O ( n log ( n )), что делает его очень быстрым на практике. Но при вводе в наихудшем случае его производительность снижается до O ( n 2 ). Кроме того, при реализации с политикой «сначала кратчайшее», сложность пространства для наихудшего случая ограничивается O (log ( n )).
- Heapsort имеет время O (n), когда все элементы одинаковы. Heapify занимает O (n) раз, а затем удаление элементов из кучи занимает O (1) раз для каждого из n элементов. Время выполнения увеличивается до O (nlog (n)), если все элементы должны быть разными.
- Bogosort имеет время O (n), когда элементы сортируются на первой итерации. На каждой итерации проверяются все ли элементы в порядке. Нет! возможные перестановки; со сбалансированным генератором случайных чисел почти каждая перестановка массива получается за n! итераций. У компьютеров ограниченная память, поэтому генерируемые числа циклически повторяются; может быть невозможно достичь каждой перестановки. В худшем случае это приводит к O (∞) времени, бесконечному циклу.
Структуры данных [ править ]
| Структура данных | Сложность времени | Космическая сложность | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Среднее: индексирование | Среднее: поиск | Средняя: вставка | Средняя: удаление | Худшее: индексирование | Худшее: поиск | Худшее: вставка | Худшее: удаление | Наихудший | |
| Базовый массив | О (1) | О ( п ) | - | - | О (1) | О ( п ) | - | - | О ( п ) |
| Динамический массив | О (1) | О ( п ) | О ( п ) | - | О (1) | О ( п ) | О ( п ) | - | О ( п ) |
| Односвязный список | О ( п ) | О ( п ) | О (1) | О (1) | О ( п ) | О ( п ) | О (1) | О (1) | О ( п ) |
| Двусвязный список | О ( п ) | О ( п ) | О (1) | О (1) | О ( п ) | О ( п ) | О (1) | О (1) | О ( п ) |
| Хеш-таблица | - | О (1) | О (1) | О (1) | - | О ( п ) | О ( п ) | О ( п ) | О ( п ) |
| Дерево двоичного поиска | - | O (журнал ( n )) | O (журнал ( n )) | O (журнал ( n )) | - | О ( п ) | О ( п ) | О ( п ) | О ( п ) |
| B-дерево | - | O (журнал ( n )) | O (журнал ( n )) | O (журнал ( n )) | - | O (журнал ( n )) | O (журнал ( n )) | O (журнал ( n )) | О ( п ) |
| Красно-черное дерево | - | O (журнал ( n )) | O (журнал ( n )) | O (журнал ( n )) | - | O (журнал ( n )) | O (журнал ( n )) | O (журнал ( n )) | О ( п ) |
| Дерево AVL | - | O (журнал ( n )) | O (журнал ( n )) | O (журнал ( n )) | - | O (журнал ( n )) | O (журнал ( n )) | O (журнал ( n )) | О ( п ) |
- Линейный поиск по списку из n элементов. В самом худшем случае поиск должен посещать каждый элемент один раз. Это происходит, когда искомое значение является либо последним элементом в списке, либо его нет. Однако в среднем, если искомое значение находится в списке и каждый элемент списка с равной вероятностью будет искомым значением, поиск посещает только n / 2 элементов.
См. Также [ править ]
- Алгоритм сортировки - область, в которой проводится большой анализ производительности различных алгоритмов.
- Структура данных поиска - любая структура данных, позволяющая эффективно извлекать определенные элементы.
- Анализ схем наихудшего случая
- Сглаженный анализ
- Интервальный конечный элемент
- Обозначение Big O
Ссылки [ править ]
- ^ Введение в алгоритмы (Кормен, Лейзерсон, Ривест и Штейн) 2001, глава 2 «Начало работы». В лучшем случае сложности дает нижнюю границу времени работы алгоритма для любых экземпляров входных данных.
- ^ Спилман, Дэниел ; Тэн, Shang-Хуо (2009), "сглаженный анализ: попытка объяснить поведение алгоритмов на практике" (PDF) , коммуникации АСМА , ACM, 52 (10): 76-84, DOI : 10,1145 / 1562764,1562785
- ^ «Сложность наихудшего случая» (PDF) . Архивировано (PDF) из оригинала 21.07.2011 . Проверено 30 ноября 2008 .
