Используется ли сглаженный анализ за пределами академии?

Question

Сделал сглаженный анализ Найти свой путь в анализ основного потока алгоритмов? Обычно дизайнеры алгоритма применяют сглаженный анализ на свои алгоритмы?

Answer 1

Я могу ошибаться, но я рассматриваю сглаженный анализ как способ объяснять Поведение алгоритмов, которые имеют плохие теоретические гарантии (Simplex, K-Means и так далее). Я не уверен, что это значит использовать Сглаженный анализ на практике, за исключением того, чтобы оправдать использование конкретной эвристики с плохими результатами в худшем случае («моя эвристика имеет поведение бла-бла, но сглаженный анализ указывает на то, что он будет хорошо на практике и т. Д.»)

Answer 2

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

• Метод приближения. Здесь вы используете много упрощающих предположений, чтобы попытаться прогнозировать время выполнения алгоритма. Подобно тому, что делают физики -теоретики (используются).
• Эксперименты. Вы запускаете свой алгоритм и измеряете несколько статистических данных - сколько времени проводилось в каждую часть, сколько раз каждая функция называлась, как часто проводилась каждая ветвь и так далее. Эта информация может быть использована для оптимизации алгоритма. Экспериментирование также используется для выяснения того, выполняются ли некоторые приближения при анализе работы алгоритма на практике или нет.

Тем не менее, я не думаю, что на практике очень часто анализируется алгоритм, кроме как добавить текст наполнителя в связанную академическую публикацию. Основное внимание уделяется разработке программного обеспечения или на оптимизации низкого уровня, в зависимости от предмета.

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