Предположим, у меня есть список функций, например
Как мне отсортировать их асимптотически, т.е. после отношения, определенного
,
при условии, что они действительно попарно сопоставимы (см. также здесь )? Использование определения кажется неудобным, и зачастую трудно доказать существование подходящих констант и .
Это касается мер сложности, поэтому нас интересует асимптотическое поведение при , и мы предполагаем, что все функции принимают только неотрицательные значения ( ).
Ответы:
Если вы хотите строгое доказательство, следующая лемма часто полезна, соответственно. более удобный, чем определения.
Благодаря этому вы сможете упорядочить большинство функций, возникающих при анализе алгоритмов¹. В качестве упражнения докажи это!
Конечно, вы должны быть в состоянии рассчитать пределы соответственно. Вот некоторые полезные приемы, чтобы разбить сложные функции на базовые:
В более общем смысле: если у вас есть выпуклая, непрерывно дифференцируемая и строго возрастающая функцияh так что вы можете переписать свой коэффициент как
сg∗∈Ω(1) и
,limn→∞f∗(n)g∗(n)=∞
тогда
.limn→∞f(n)g(n)=∞
Смотрите здесь для строгого доказательства этого правила (на немецком языке).
Рассмотрим продолжение ваших функций над реалами. Теперь вы можете использовать правило L'Hôpital ; будьте внимательны к его условиям²!
Когда появляются факториалы, используйте формулу Стирлинга :
Также полезно сохранить пул базовых отношений, которые вы доказываете один раз и используете часто, например:
логарифмы растут медленнее, чем полиномы, т.е.
для всех α , β > 0 .(logn)α∈o(nβ) α,β>0
порядок полиномов:
для всехα<β.nα∈o(nβ) α<β
полиномы растут медленнее, чем экспоненты:
для всехαиc>1.nα∈o(cn) α c>1
Может случиться так, что приведенная выше лемма неприменима, потому что предел не существует (например, когда функции колеблются). В этом случае рассмотрим следующую характеристику классов Ландау с использованием Limes улучшенный / низший :
Проверьте здесь и здесь, если вас смущают мои записи.
¹ Примечание: мой коллега написал функцию Mathematica, которая успешно выполняет это для многих функций, поэтому лемма действительно сводит задачу к механическим вычислениям.
² Смотрите также здесь .
источник
Limit[f[n]/g[n], n -> Infinity]
и выполнить различие в регистре.Другой совет: иногда применение монотонной функции (например, log или exp) к функциям делает вещи более понятными.
источник
Скиена приводит отсортированный список отношений доминирования между наиболее распространенными функциями в своей книге «Руководство по разработке алгоритмов»:
Hereα(n) denotes the inverse Ackermann function.
источник
Совет: нарисуйте графики этих функций, используя что-то вроде Wolfram Alpha, чтобы понять, как они растут. Обратите внимание, что это не очень точно, но если вы попробуете это для достаточно больших чисел, вы должны увидеть сравнительные закономерности роста. Это, конечно, не заменит доказательства.
Например, попробуйте: построить график (log (n)) от 1 до 10000, чтобы увидеть отдельный график или график (log (n)), и построить график (n) от 1 до 10000, чтобы увидеть сравнение.
источник
I suggest proceeding according to the definitions of various notations. Start with some arbitrary pair of expressions, and determine the order of those, as outlined below. Then, for each additional element, find its position in the sorted list using binary search and comparing as below. So, for example, let's sortnloglogn and 2n , the first two functions of n, to get the list started.
We use the property thatn=2logn to rewrite the first expression as nloglogn=(2logn)loglogn=2lognloglogn . We could then proceed to use the definition to show that nloglogn=2lognloglogn∈o(2n) , since for any constant c>0 , there is an n0 such that for n≥n0 , c(nloglogn)=c(2lognloglogn)<2n .
Next, we try3n . We compare it to 2n , the largest element we have placed so far. Since 3n=(2log3)n=2nlog3 , we similarly show that 2n∈o(3n)=o(2nlog3) .
Etc.
источник
Вот список из Википедии : чем ниже в таблице, тем больше класс сложности;Nм еПостоянное времяОбратное время по АккерманнуПовторное логарифмическое времяЛог-логарифмическийЛогарифмическое времяПолилогарифмическое времяДробная силаЛинейное времявремя "n log star n"Квазилинейное времяКвадратичное времяКубическое времяПолиномиальное времяКвазиполиномиальное времяСубэкспоненциальное время (первое определение)Субэкспоненциальное время (второе определение)Экспоненциальное время (с линейным показателем)Экспоненциальное времяФакториальное времяПродолжительностьO (1)O (a(n))O ( журнал*н )O (nlogн )O ( журналн )р о л у(logн )O ( nс) , где 0 < c < 1O (n)O (n log*н )O (n logн )O ( n2)O ( n3)р о л у( n ) = 2O ( журналн )2О (ролу( журналн ) )O ( 2Nε) , ϵ > 02o (n)2O (n)2р о л у( н )O (n!)
note :poly(x)=xO(1)
источник