Что такое эффективный алгоритм?

10

С точки зрения асимптотического поведения, что считается «эффективным» алгоритмом? Каков стандарт / причина для рисования линии в этой точке? Лично я бы подумал, что все, что я могу наивно назвать «подполиномом», такое, что такое как , будет эффективным, а все, что будет "неэффективным". Однако я слышал, что все, что имеет любой полиномиальный порядок, можно назвать эффективным. В чем причина?f(n)=o(n2) Ω ( n 2 )n1+ϵΩ(n2)

Роберт С. Барнс
источник

Ответы:

11

Это зависит от контекста. В теоретической информатике обычно каждый алгоритм за полиномиальное время считается «эффективным». В алгоритмах аппроксимации, например, время выполнения будет считаться эффективным, даже если на практике его нельзя будет использовать при любом разумном значении . Алгоритм для SAT, который выполняется в был бы удивительным прорывом. ϵ n 2 100n1/ϵ1/ϵϵn2100

В классической алгоритмике, т. Е. Алгоритмах 80-х и ранее, время выполнения ниже или около того (умножение матрицы, согласование минимальных затрат, потоки, линейное программирование) считается эффективным. Я бы сказал, что они все еще считаются эффективными. Конечно, алгоритм не считается эффективным, если известен алгоритм , как, например, для сортировки.n 2 n log nn3n2nlogn

В настоящее время существует тенденция к сублинейным алгоритмам или потоковым алгоритмам, способным обрабатывать терабайты данных. Попробуйте использовать матричное умножение, чтобы вычислить рейтинг страниц всех страниц в индексе Google. Это не сработает.

Конечно, хотя это и полезно, асимптотическое время выполнения алгоритма не рассказывает всей истории. Существуют алгоритмы с хорошей асимптотической средой выполнения, но такие огромные константы, что их эффективно использовать нельзя. Когда-либо. Липтон называет их Галактическими Алгоритмами . Роберт Седжвик даже заявляет, что наихудшие границы «часто бесполезны для предсказания, часто бесполезны для гарантий» и «анализ наихудшего случая бесполезен для предсказания производительности» в своем выступлении «Возвращение науки в информатику» .

adrianN
источник
9
Вкратце: эффективность - это то, что решает вашу проблему в сроки, которые вам подходят.
Рафаэль
На самом деле это не требует своего собственного ответа, но BPP, который является классом функций с полиномиальным временем выполнения (как описано в ответе) со случайностью, часто считается эффективным. Другими словами, вышеприведенное верно, но компьютерам, как правило, разрешен доступ к случайности для выполнения вычислений. Одним из наиболее важных практических применений случайности является хеширование.
SamM
Может быть, «эффективный» не совсем правильная терминология? Я просто просматривал одну из моих книг по исчислениям, и автор называет полиномиальные среды выполнения «податливыми», а экспоненциальные среды выполнения - «неразрешимыми».
Роберт С. Барнс
1
@ RobertS.Barnes: разные слова, та же проблема.
Рафаэль
4

O(logcn)c>0 O(logn)

Питер
источник
3

Причиной этого является то, что с точки зрения асимптотического поведения полиномиальная скорость роста тривиально меньше, чем суперполиномиальная скорость роста. На практике алгоритм полиномиального времени работает намного быстрее, чем алгоритм суперполиномиального времени, когда размер входных данных увеличивается.

O(n2000)O(n5)

O(n2)

Массимо Кафаро
источник
3

Теоретически алгоритм считается эффективным, если время его наихудшего случая ограничено полиномом по входной длине. Причина в том, что полиномы имеют хорошие свойства замыкания. Добавление, умножение, составление полиномов - это операции, которые дают полиномы, и они хороши, если вы сводите проблемы друг к другу.

Конечно, разрыв между полиномом и экспонентой становится очень очень большим, так как длина входного сигнала увеличивается, поэтому алгоритмы за полиномиальное время намного лучше. На практике алгоритм полиномиального времени может занять много времени до завершения, но это может быть случай, когда это оптимальный алгоритм (наилучший из возможных), и в этом случае я бы сказал, что он эффективен.

saadtaame
источник
Хотя я могу понять, что если что-то является самым быстрым из известных алгоритмов для конкретной проблемы, то с этой точки зрения его можно считать «эффективным», мне трудно представить что-либо, что работает в polytime, как эффективное. :-)
Роберт С. Барнс
Для полиномиальных сред выполнения «эффективный» - это просто слово, и вводящее в заблуждение.
Рафаэль
@Raphael Может быть, лучше использовать слово tractable ...?
Роберт С. Барнс
1
@ RobertS.Barnes: Не намного лучше, имхо. «Трактабельность» так же относительна, как и «эффективна».
Рафаэль