Используется ли Smoothed Analysis вне академических кругов?

24

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

algorithms complexity-theory algorithm-analysis Жиль "ТАК - перестань быть злым"
источник
11
Применяют ли люди какой-либо анализ сложности к своим алгоритмам вне академических кругов?
Дэйв Кларк,
2
Что говорит @DaveClarke; возможно, ему следует попросить провести строгий (или нетривиальный) анализ. Я ожидаю, что многие практики посмотрят на свои алгоритмы, посчитают глубину вложенности цикла и скажут: «Это !». O(n3)
Рафаэль
3
В поисках любого использования сглаженного анализа, кроме Simplex, я нашел список, созданный одним из парней, который открыл методику.
Рафаэль
1
@DaveClarke как насчет людей, работающих в IBM, HP или NTT? Разве они не должны использовать такой анализ?
Маркос Вильягра
1
@DaveClarke Я делаю.
Кевин

Ответы:

12

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

Суреш
источник
2
Проблема в том, что до сих пор большие успехи в сглаженном анализе были в объяснении текущей практики, поэтому практикующие могли бы просто отреагировать, сказав: «Хорошо, что все, что я делал, может быть показано, что имеет смысл» :). Я не знаю, решил ли кто-то использовать до сих пор менее известную эвристику из-за сглаженного анализа.
Суреш
Формальный сглаженный анализ очень труден, нет причин, по которым никто не должен практиковать его. С другой стороны, если вы рассматриваете его как эвристику, используемую для анализа алгоритма (а именно, вход является полуслучайным), то он, вероятно, используется постоянно.
Юваль Фильмус
3

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

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

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

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

Юваль Фильмус
источник
« В то время как в научных кругах цель состоит в том, чтобы найти доказуемо-корректную верхнюю границу времени выполнения» - то есть цель, а не цель. Существует также много работы по анализу среднего случая, даже если среднестатистический студент CS может не увидеть большую часть этого (потому что это относительно трудно). «Чтобы понять, как работает алгоритм», возможно, является основой всей алгоритмики в научных кругах.
Рафаэль