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