Что это значит, когда мы говорим, что алгоритм асимптотически более эффективен, чем ?
- будет лучшим выбором для всех входов.
- будет лучшим выбором для всех входов, кроме небольших.
- будет лучшим выбором для всех входов, кроме больших.
- будет лучшим выбором для небольших входов.
Ссылка на этот вопрос здесь.
http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/
Я думал, что алгоритм, более асимптотически эффективный, должен работать для всех входных данных, но я не понимаю причину «он работает для всех входных сигналов, кроме небольших».
Ответы:
Во-первых, оба алгоритма «работают» для всех входов. Вопрос в производительности.
Ответы на этот вопрос довольно дерьмовые. Один из способов сказать, что один алгоритм асимптотически более эффективен, чем другой, - это если есть некоторый (специфичный для проблемы) размер входного файла, такой, что для любого большего входного размера более эффективный алгоритм будет выполнять меньше «вычислительных шагов», обычно с помощью некоторой абстрактной меры, например количество сравнений.
Идея ответов состоит в том, что асимптотически более эффективный алгоритм может все еще потребовать большего количества шагов перед этим входным размером. Это может быть так , что асимптотически более эффективный алгоритм требует меньше шагов для всех входов, но он не должен быть так и на практике , как правило , не является. Поэтому лучше сформулировать «правильный» ответ: « будет лучшим выбором для всех входов, кроме, возможно, небольших».Икс
Формулировка все еще не так велика, хотя. Во-первых, многие факторы влияют на решение о том, какой алгоритм является «лучшим выбором», но я дам им понять, что цель в этом случае достаточно ясна. Настоящая проблема - «маленькая» и «большая». Одна из моих любимых статей - «Самый быстрый и короткий алгоритм для всех хорошо определенных задач» . В этой статье описывается алгоритм, который дает любую спецификацию функции и доказательство того, что она может быть вычислена за полиномиальное время, будет вычислять эту функцию в оптимальной временной сложности с коэффициентом плюс аддитивный член. Например, если я предоставлю ему реализацию пузырьковой сортировки в качестве спецификации функции и простое доказательство того, что это былаO ( n 2 ) O ( n lg n ) 5 c n lg n + o ( n lg n ) c o ( n lg n )5 O ( n2) , он будет производить алгоритм сортировки, который был . Фактически, это дало бы алгоритм, который был бы где - постоянный фактор асимптотически * оптимального алгоритма. Это потрясающе. Есть только одна проблема: постоянный член - скрытый вO ( n lgн ) 5 c n lgn + o ( n lgн ) с o ( n lgн ) в этом примере - делает алгоритм почти наверняка совершенно невозможным практически для любой реальной проблемы. Что я подразумеваю под «совершенно неосуществимым»? Я имею в виду, что тепловая смерть вселенной произойдет много раз, прежде чем этот алгоритм завершится. Тем не менее, для подходящих «больших» входов это будет быстрее, чем пузырьковая сортировка. Моя точка зрения заключается в том, что почти наверняка физически невозможно записать каким-либо образом «достаточно большой» вход, не говоря уже о вычислениях на нем.
В любом случае, как бы я сказал правильный ответ: « требует меньше шагов, чем на достаточно больших входах». Это все еще немного расплывчато, поскольку существует множество понятий «шаг», которые могут применяться, и алгоритм может быть асимптотически более эффективным по одной метрике и менее эффективным по другой. Эта формулировка избегает ценностного суждения о «лучшем выборе»; Есть много причин для выбора асимптотически менее эффективных алгоритмов или даже менее эффективных алгоритмов, когда заданы постоянные факторы / термины, такие как эффективность кэширования или простота реализации.YИкс Y
* Здесь есть тонкость. Асимптотически оптимальный алгоритм может иметь худший постоянный коэффициент , чем асимптотически неоптимальный алгоритм. Я думаю, что он будет иметь наилучшее значение для любого асимптотически оптимального алгоритма, но возможно, что для выживания небольшого выигрыша в асимптотической эффективности добавится огромная сложность, которая значительно увеличивает постоянный коэффициент.сс с
источник
Что люди обычно имеют в виду, когда говорят что-то вроде этого:
Здесь применимы многие предостережения: необходимо указать , и мы должны точно определить, что означает «стоимость времени выполнения». Время почти никогда не является предметом исследования. Есть много других мер стоимости. Это неясно , если Ландау обозначение делает любое полезное заявление об эффективности. И так далее.Икс
В частности, ни одно из предложенных вами утверждений не следует, хотя люди часто предлагают второе.
К сожалению, более широкое сообщество людей, имеющих дело с алгоритмами, использует терминологию, которая ради простоты граничит с пустыми. (Делать точные и полезные утверждения об алгоритмах сложно!)
Вас могут заинтересовать наши справочные вопросы .
Обратите внимание, что это не обычное определение! Если и , мы бы не сказали, что это «асимптотически лучше». Учитывая все предостережения анализа, сводящие производительность алгоритма к одному числу, нельзя утверждать, что один был «лучше», чем другой.T B ( n ) = nTA( n ) = n + 1 TВ( n ) = n
Я рекомендую вам изучать информатику из ресурсов CS, а не у программистов, которые когда-то читали о материалах в Википедии. (Да, это грубо, но я видел слишком много лжи, распространяемой в кругах программистов, даже на SO.)
источник
«Асимптотически более эффективный» означает «более эффективный для всех задач выше определенного размера». Он не говорит, что такое «определенный размер», и не говорит, что происходит до этого «определенного размера».
Таким образом, все ответы, кроме второго, явно неверны, потому что «Асимптотически более эффективный» вообще ничего не говорит о небольших размерах ввода. Но второй тоже проблемный.
На практике часто полезно проверить, для какого размера входного сигнала асимптотически лучший алгоритм на самом деле быстрее, и какое требуется время для входных данных, где он быстрее, а иногда алгоритм будет быстрее только для проблемных размеров, которые практически не могут быть решенным в любом случае. Если алгоритм A побеждает алгоритм B, но только для задач, каждая из которых занимает лет или более, то A не очень помогает.1015
источник