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