Что значит сказать «Асимптотически эффективнее»?

12

Что это значит, когда мы говорим, что алгоритм X асимптотически более эффективен, чем ?Y

  • X будет лучшим выбором для всех входов.
  • X будет лучшим выбором для всех входов, кроме небольших.
  • X будет лучшим выбором для всех входов, кроме больших.
  • Y будет лучшим выбором для небольших входов.

Ссылка на этот вопрос здесь.

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/


Я думал, что алгоритм, более асимптотически эффективный, должен работать для всех входных данных, но я не понимаю причину «он работает для всех входных сигналов, кроме небольших».

Гаррик
источник
большой вход выставляет бутылочную горловину в алгоритме. Это то, что я бы поставил в инженерном плане.
Апиват Чантавибул

Ответы:

14

Во-первых, оба алгоритма «работают» для всех входов. Вопрос в производительности.

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

Идея ответов состоит в том, что асимптотически более эффективный алгоритм может все еще потребовать большего количества шагов перед этим входным размером. Это может быть так , что асимптотически более эффективный алгоритм требует меньше шагов для всех входов, но он не должен быть так и на практике , как правило , не является. Поэтому лучше сформулировать «правильный» ответ: « будет лучшим выбором для всех входов, кроме, возможно, небольших».Икс

Формулировка все еще не так велика, хотя. Во-первых, многие факторы влияют на решение о том, какой алгоритм является «лучшим выбором», но я дам им понять, что цель в этом случае достаточно ясна. Настоящая проблема - «маленькая» и «большая». Одна из моих любимых статей - «Самый быстрый и короткий алгоритм для всех хорошо определенных задач» . В этой статье описывается алгоритм, который дает любую спецификацию функции и доказательство того, что она может быть вычислена за полиномиальное время, будет вычислять эту функцию в оптимальной временной сложности с коэффициентом плюс аддитивный член. Например, если я предоставлю ему реализацию пузырьковой сортировки в качестве спецификации функции и простое доказательство того, что это былаO ( n 2 ) O ( n lg n ) 5 c n lg n + o ( n lg n ) c o ( n lg n )5О(N2), он будет производить алгоритм сортировки, который был . Фактически, это дало бы алгоритм, который был бы где - постоянный фактор асимптотически * оптимального алгоритма. Это потрясающе. Есть только одна проблема: постоянный член - скрытый вО(NЛ.Г.N)5сNЛ.Г.N+о(NЛ.Г.N)со(NЛ.Г.N)в этом примере - делает алгоритм почти наверняка совершенно невозможным практически для любой реальной проблемы. Что я подразумеваю под «совершенно неосуществимым»? Я имею в виду, что тепловая смерть вселенной произойдет много раз, прежде чем этот алгоритм завершится. Тем не менее, для подходящих «больших» входов это будет быстрее, чем пузырьковая сортировка. Моя точка зрения заключается в том, что почти наверняка физически невозможно записать каким-либо образом «достаточно большой» вход, не говоря уже о вычислениях на нем.

В любом случае, как бы я сказал правильный ответ: « требует меньше шагов, чем на достаточно больших входах». Это все еще немного расплывчато, поскольку существует множество понятий «шаг», которые могут применяться, и алгоритм может быть асимптотически более эффективным по одной метрике и менее эффективным по другой. Эта формулировка избегает ценностного суждения о «лучшем выборе»; Есть много причин для выбора асимптотически менее эффективных алгоритмов или даже менее эффективных алгоритмов, когда заданы постоянные факторы / термины, такие как эффективность кэширования или простота реализации.YИксY

* Здесь есть тонкость. Асимптотически оптимальный алгоритм может иметь худший постоянный коэффициент , чем асимптотически неоптимальный алгоритм. Я думаю, что он будет иметь наилучшее значение для любого асимптотически оптимального алгоритма, но возможно, что для выживания небольшого выигрыша в асимптотической эффективности добавится огромная сложность, которая значительно увеличивает постоянный коэффициент.ссс

Дерек Элкинс покинул ЮВ
источник
2

Что люди обычно имеют в виду, когда говорят что-то вроде этого:

Если и являются двумя функциями затрат времени выполнения алгоритмов и в модели X соответственно, то .T B A B T Ao ( T B )TATВAВTAо(TВ)

Здесь применимы многие предостережения: необходимо указать , и мы должны точно определить, что означает «стоимость времени выполнения». Время почти никогда не является предметом исследования. Есть много других мер стоимости. Это неясно , если Ландау обозначение делает любое полезное заявление об эффективности. И так далее.Икс

В частности, ни одно из предложенных вами утверждений не следует, хотя люди часто предлагают второе.

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

Вас могут заинтересовать наши справочные вопросы .


Алгоритм X называется асимптотически лучше, чем Y, если X занимает меньше времени, чем y, для всех входных размеров n, больших, чем значение n0, где n0> 0.

Обратите внимание, что это не обычное определение! Если и , мы бы не сказали, что это «асимптотически лучше». Учитывая все предостережения анализа, сводящие производительность алгоритма к одному числу, нельзя утверждать, что один был «лучше», чем другой.T B ( n ) = nTA(N)знак равноN+1TВ(N)знак равноN

Я рекомендую вам изучать информатику из ресурсов CS, а не у программистов, которые когда-то читали о материалах в Википедии. (Да, это грубо, но я видел слишком много лжи, распространяемой в кругах программистов, даже на SO.)

Рафаэль
источник
2

«Асимптотически более эффективный» означает «более эффективный для всех задач выше определенного размера». Он не говорит, что такое «определенный размер», и не говорит, что происходит до этого «определенного размера».

Таким образом, все ответы, кроме второго, явно неверны, потому что «Асимптотически более эффективный» вообще ничего не говорит о небольших размерах ввода. Но второй тоже проблемный.

103010301040

На практике часто полезно проверить, для какого размера входного сигнала асимптотически лучший алгоритм на самом деле быстрее, и какое требуется время для входных данных, где он быстрее, а иногда алгоритм будет быстрее только для проблемных размеров, которые практически не могут быть решенным в любом случае. Если алгоритм A побеждает алгоритм B, но только для задач, каждая из которых занимает лет или более, то A не очень помогает.1015

gnasher729
источник