Сортировка функций по асимптотическому росту

35

Предположим, у меня есть список функций, например

nloglog(n),2n,n!,n3,nlnn,

Как мне отсортировать их асимптотически, т.е. после отношения, определенного

fOgfO(g) ,

при условии, что они действительно попарно сопоставимы (см. также здесь )? Использование определения кажется неудобным, и зачастую трудно доказать существование подходящих констант и .Ocn0

Это касается мер сложности, поэтому нас интересует асимптотическое поведение при , и мы предполагаем, что все функции принимают только неотрицательные значения ( ).n+n,f(n)0

JAN
источник
4
Поскольку ОП так и не вернулся, я удаляю локализованные вещи и делаю из этого контрольный вопрос.
Рафаэль

Ответы:

48

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

Если c=limnf(n)g(n) существует, тогда

  • c=0 fo(g) ,
  • c(0,)fΘ(g) и
  • c=   fω(g) .

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

Конечно, вы должны быть в состоянии рассчитать пределы соответственно. Вот некоторые полезные приемы, чтобы разбить сложные функции на базовые:

  • Выразите обе функции как e и сравните показатели; если их отношение стремится к 0 или , то же самое происходит и с исходным отношением.
  • В более общем смысле: если у вас есть выпуклая, непрерывно дифференцируемая и строго возрастающая функция h так что вы можете переписать свой коэффициент как

    f(n)g(n)=h(f(n))h(g(n)) ,

    с gΩ(1) и

    ,limnf(n)g(n)=

    тогда

    .limnf(n)g(n)=

    Смотрите здесь для строгого доказательства этого правила (на немецком языке).

  • Рассмотрим продолжение ваших функций над реалами. Теперь вы можете использовать правило L'Hôpital ; будьте внимательны к его условиям²!

  • Взгляните на дискретный эквивалент Штольца-Чезаро .
  • Когда появляются факториалы, используйте формулу Стирлинга :

    n!2πn(ne)n

Также полезно сохранить пул базовых отношений, которые вы доказываете один раз и используете часто, например:

  • логарифмы растут медленнее, чем полиномы, т.е.

    для всех α , β > 0 .(logn)αo(nβ)α,β>0

  • порядок полиномов:

    для всехα<β.nαo(nβ)α<β

  • полиномы растут медленнее, чем экспоненты:

    для всехαиc>1.nαo(cn)αc>1


Может случиться так, что приведенная выше лемма неприменима, потому что предел не существует (например, когда функции колеблются). В этом случае рассмотрим следующую характеристику классов Ландау с использованием Limes улучшенный / низший :

При у нас естьcs:=lim supnf(n)g(n)

  • и0cs<fO(g)
  • .cs=0fo(g)

При у нас естьci:=lim infnf(n)g(n)

  • и0<cifΩ(g)
  • .ci=fω(g)

Более того,

  • и0<ci,cs<fΘ(g)gΘ(f)
  • .ci=cs=1fg

Проверьте здесь и здесь, если вас смущают мои записи.


¹ Примечание: мой коллега написал функцию Mathematica, которая успешно выполняет это для многих функций, поэтому лемма действительно сводит задачу к механическим вычислениям.

² Смотрите также здесь .

Рафаэль
источник
@Juho Не публично, афаик, но элементарно написать самому; вычислить Limit[f[n]/g[n], n -> Infinity]и выполнить различие в регистре.
Рафаэль
20

Другой совет: иногда применение монотонной функции (например, log или exp) к функциям делает вещи более понятными.

Суреш
источник
5
2nO(n)22nO(2n)
2
Откомандирован. Кажется, что «применить монотонную функцию» - это своего рода фольклор, который вообще не работает. Мы работали над достаточными критериями и получили то, что я написал в последней редакции моего ответа .
Рафаэль
17

Скиена приводит отсортированный список отношений доминирования между наиболее распространенными функциями в своей книге «Руководство по разработке алгоритмов»:

n!cnn3n2n1+ϵnlgnnn1/2
lg2nlgnlgnlglgnlglgnα(n)1

Here α(n) denotes the inverse Ackermann function.

Robert S. Barnes
источник
That's an oddly specific list. Many of the relations (whatever means exactly) can be summarised to a handful of more general lemmata.
Raphael
Это его нотация для отношения доминирования.
Robert S. Barnes
11

Совет: нарисуйте графики этих функций, используя что-то вроде Wolfram Alpha, чтобы понять, как они растут. Обратите внимание, что это не очень точно, но если вы попробуете это для достаточно больших чисел, вы должны увидеть сравнительные закономерности роста. Это, конечно, не заменит доказательства.

Например, попробуйте: построить график (log (n)) от 1 до 10000, чтобы увидеть отдельный график или график (log (n)), и построить график (n) от 1 до 10000, чтобы увидеть сравнение.

Дейв Кларк
источник
9
Should we really recommend vodoo?
Raphael
+1 за предложение рисовать графики функций, хотя связанные графики довольно запутаны, если вы не знаете, что они означают.
Tsuyoshi Ito
1
Take a graph as a hint what you might want to prove. That hint may be wrong of course.
gnasher729
8

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 sort nloglogn and 2n, the first two functions of n, to get the list started.

We use the property that n=2logn to rewrite the first expression as nloglogn=(2logn)loglogn=2lognloglogn. We could then proceed to use the definition to show that nloglogn=2lognloglogno(2n), since for any constant c>0, there is an n0 such that for nn0, c(nloglogn)=c(2lognloglogn)<2n.

Next, we try 3n. We compare it to 2n, the largest element we have placed so far. Since 3n=(2log3)n=2nlog3, we similarly show that 2no(3n)=o(2nlog3).

Etc.

Patrick87
источник
2

Вот список из Википедии : чем ниже в таблице, тем больше класс сложности;

NaмеПродолжительностьПостоянное времяО(1)Обратное время по АккерманнуО(a(N))Повторное логарифмическое времяО(журнал*N)Лог-логарифмическийО(NжурналN)Логарифмическое времяО(журналN)Полилогарифмическое времяпоLY(журналN)Дробная силаО(Nс),where 0<c<1Linear timeO(n)"n log star n" timeO(nlogn)Quasilinear timeO(nlogn)Quadratic timeO(n2)Cubic timeO(n3)Polynomial timepoly(n)=2O(logn)Quasi-polynomial time2O(poly(logn))Sub-exponential time (first definition)O(2nϵ),ϵ>0Sub-exponential time (second definition)2o(n)Exponential time(with linear exponent)2O(n)Exponential time2poly(n)Factorial timeO(n!)

note : poly(x)=xO(1)

kelalaka
источник
1
Также интересно, как из таблицы видно, что 2NжурналNо(N!), Хотя в таблице вы ссылки на несколько точной, одна связана там (и который вы скопировали) о классах сложности, которые не полезно , что нужно смешать здесь. Запись Ландау не о «времени».
Рафаэль
1
Я поставил это так, чтобы названия классов сложности можно было говорить прямо здесь. Да, Ландау больше о конкретном типе алгоритма в криптографии.
Келалака
1
Я возражаю против некоторых взглядов @ Рафаэля. Я был математиком и преподавателем в течение многих лет. Я полагаю, что, помимо доказательства этих вещей, такой большой стол легко и значительно повышает интуицию людей. И названия асимптотических классов помогают людям запомнить и много общаться.
Apass.Jack
1
@ Apass.Jack В моем опыте преподавания, когда мне дают стол, многие ученики выучат его наизусть и не смогут заказать ни одну функцию, отсутствующую в столе. Обратите внимание, что этот эффект объясняет многие вопросы, касающиеся асимптотического роста, которые появляются на этом сайте. Тем не менее, конечно, мы будем использовать леммы, подразумеваемые таблицей, если это облегчает доказательства, но это происходит после изучения способов проверки таблицы. (Чтобы подчеркнуть этот момент, людям, которые приходят сюда , не нужна помощь в чтении со стола. Им нужна помощь в доказательстве отношений.)
Рафаэль
1
@kelalaka "Да, Ландау больше о конкретном типе алгоритма в криптографии." - это даже не имеет смысла. Обозначение Ландау является сокращением для описания свойств математических функций. Это не имеет ничего общего с алгоритмами, не говоря уже о криптографии.
Рафаэль