Sortowanie funkcji według asymptotycznego wzrostu

35

Załóżmy, że mam na przykład listę funkcji

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

Jak sortować je asymptotycznie, tj. Według relacji zdefiniowanej przez

faOsolfaO(sol) ,

zakładając, że rzeczywiście są one porównywalne parami (patrz także tutaj )? Używanie definicji O wydaje się niewygodne i często trudno jest udowodnić istnienie odpowiednich stałych do i n0 .

Chodzi o miary złożoności, dlatego interesuje nas zachowanie asymptotyczne, ponieważ n+ , i zakładamy, że wszystkie funkcje przyjmują tylko wartości nieujemne ( n,fa(n)0 ).

JAN
źródło
4
Ponieważ OP nigdy nie wrócił, usuwam zlokalizowane pliki i robię z tego pytanie referencyjne.
Raphael

Odpowiedzi:

48

Jeśli potrzebujesz ścisłego dowodu, często przydatny jest następujący lemat. bardziej przydatne niż definicje.

Jeśli do=limnfa(n)sol(n) istnieje zatem

  • do=0 fao(sol) ,
  • ido(0,)faΘ(sol)
  • .do=   faω(sol)

Dzięki temu powinieneś być w stanie zamówić większość funkcji pojawiających się w analizie algorytmów¹. Jako ćwiczenie udowodnij to!

Oczywiście musisz być w stanie odpowiednio obliczyć limity. Oto kilka przydatnych sztuczek pozwalających rozbić skomplikowane funkcje na podstawowe:

  • Wyraź obie funkcje jako i porównaj wykładniki; jeśli ich stosunek ma tendencję do 0 lub , to samo dzieje się z ilorazem pierwotnym.mi0
  • Mówiąc bardziej ogólnie: jeśli masz wypukłą, ciągle różnicowalną i ściśle zwiększającą się funkcję , abyś mógł ponownie zapisać swój iloraz jakoh

    ,fa(n)sol(n)=h(fa(n))h(sol(n))

    za pomocą isolΩ(1)

    ,limnf(n)g(n)=

    następnie

    .limnf(n)g(n)=

    Zobacz tutaj dokładny dowód tej reguły (w języku niemieckim).

  • Zastanów się nad kontynuacją swoich funkcji nad rzeczywistością. Możesz teraz użyć reguły L'Hôpital ; uważaj na jego warunki²!

  • Zobacz dyskretny odpowiednik Stolz – Cesàro .
  • Kiedy wyskakują silnie, użyj wzoru Stirlinga :

    n!2πn(ne)n

Przydatne jest również utrzymanie puli podstawowych relacji, które udowodnisz raz i których często używasz, takich jak:

  • logarytmy rosną wolniej niż wielomiany, tj

    dla wszystkich α , β > 0 .(logn)αo(nβ)α,β>0

  • kolejność wielomianów:

    dla wszystkichα<β.nαo(nβ)α<β

  • wielomiany rosną wolniej niż wykładnicze:

    dla wszystkichαic>1.nαo(cn)αc>1


Może się zdarzyć, że powyższy lemat nie ma zastosowania, ponieważ limit nie istnieje (np. Gdy funkcje oscylują). W takim przypadku weź pod uwagę następującą charakterystykę klas Landaua, stosując limonki lepsze / gorsze :

Z mamycs:=lim supnf(n)g(n)

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

Za pomocą mamyci:=lim infnf(n)g(n)

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

Ponadto,

  • i0<ci,cs<fΘ(g)gΘ(f)
  • .ci=cs=1fasol

Sprawdź tu i tutaj, jeśli moja notacja mnie myli.


¹ Nota bene: Mój kolega napisał funkcję Mathematica, która robi to z powodzeniem dla wielu funkcji, więc lemat naprawdę redukuje zadanie do obliczeń mechanicznych.

² Zobacz także tutaj .

Raphael
źródło
@Juho Nie publicznie, afaik, ale podstawową sprawą jest napisanie siebie; oblicz Limit[f[n]/g[n], n -> Infinity]i rozróżnij wielkość liter.
Raphael
20

Kolejna wskazówka: czasami zastosowanie funkcji monotonicznej (takiej jak log lub exp) do funkcji sprawia, że ​​wszystko jest wyraźniejsze.

Suresh
źródło
5
Należy to zrobić ostrożnie: , ale 2 2 nO ( 2 n ) . 2nO(n)22nO(2n)
Shaull
2
Oddelegowany. „Zastosuj funkcję monotoniczną” wydaje się być rodzajem folkloru, który nie działa w ogóle. Pracowaliśmy nad wystarczającymi kryteriami i opracowaliśmy to, co zamieściłem w najnowszej wersji mojej odpowiedzi .
Raphael
17

Skiena przedstawia posortowaną listę relacji dominacji między najczęstszymi funkcjami w swojej książce, The Algorytm Design Manual:

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

Tutaj α(n) oznacza odwrotną funkcję Ackermanna .

Robert S. Barnes
źródło
To dziwnie konkretna lista. Wiele z tych stosunków (co środki dokładnie) można streścić do kilku bardziej ogólnych form hasłowych.
Raphael
To jego notacja dla relacji dominującej.
Robert S. Barnes,
11

Wskazówka: narysuj wykresy tych funkcji za pomocą czegoś takiego jak Wolfram Alpha, aby poczuć, jak się rozwijają. Zauważ, że nie jest to zbyt precyzyjne, ale jeśli spróbujesz tego dla wystarczająco dużych liczb, powinieneś zobaczyć porównawcze wzorce wzrostu. To oczywiście nie zastąpi dowodu.

Np. Spróbuj: dziennik wydruku (log (n)) od 1 do 10000, aby zobaczyć pojedynczy wykres lub dziennik wydruku (log (n)) i dziennik wydruku (n) od 1 do 10000, aby zobaczyć porównanie.

Dave Clarke
źródło
9
Czy naprawdę powinniśmy polecać vodoo ?
Raphael
+1 za sugerowanie rysowania wykresów funkcji, chociaż połączone wykresy są raczej mylące, chyba że wiesz, co one oznaczają.
Tsuyoshi Ito
1
Weź wykres jako wskazówkę, co możesz chcieć udowodnić. Ta wskazówka może być oczywiście błędna.
gnasher729
8

Proponuję postępować zgodnie z definicjami różnych zapisów. Rozpocznij od dowolnej pary wyrażeń i określ ich kolejność, jak opisano poniżej. Następnie dla każdego dodatkowego elementu znajdź jego pozycję na posortowanej liście za pomocą wyszukiwania binarnego i porównania, jak poniżej. Na przykład posortujmy i 2 n , pierwsze dwie funkcje n, aby rozpocząć listę.nloglogn2n

n=2lognnloglogn=(2logn)loglogn=2lognloglognnloglogn=2lognloglogno(2n)c>0n0nn0c(nloglogn)=c(2lognloglogn)<2n

3n2n3n=(2log3)n=2nlog32)no(3)n)=o(2)nlog3))

Itp.

Patrick87
źródło
2

Oto lista z Wikipedii , im niższa w tabeli, tym większa klasa złożoności;

N.zammiCzas trwaniaStały czasO(1)Czas odwrotny AckermannaO(za(n))Iterowany czas logarytmicznyO(logn)LogarytmicznaO(nlogn)Czas logarytmicznyO(logn)Czas polilogarytmicznypoly(logn)Moc ułamkowaO(ndo),gdzie 0<do<1Czas liniowyO(n)Czas „n log star n”O(nlogn)Czas quasi-liniowyO(nlogn)Czas kwadratowyO(n2))Czas sześciennyO(n3))Czas wielomianowypoly(n)=2)O(logn)Czas quasi-wielomianowy2)O(poly(logn))Czas podwykładniczy (pierwsza definicja)O(2)nϵ),ϵ>0Czas podwykładniczy (druga definicja)2)o(n)Czas wykładniczy (z wykładnikiem liniowym)2)O(n)Czas wykładniczy2)poly(n)Czas czynnikowyO(n!)

Uwaga : poly(x)=xO(1)

Kelalaka
źródło
1
Ciekawe, jak sugeruje to tabela 2)nlogno(n!). Natomiast tabela ty odwołuje się do nieco dokładne, jeden połączony jest (i które zostały skopiowane) wynosi około klasami złożoności, co jest nie pomocnym rozwiązaniem mieszać tutaj. Notacja Landaua nie dotyczy „czasu”.
Raphael
1
Podaję to, aby nazwa klas złożoności mogła być tutaj omawiana. Tak, Landau bardziej dotyczy określonego rodzaju algorytmu w kryptografii.
kelalaka
1
Sprzeciwiam się niektórym opiniom @ Raphael. Od wielu lat jestem matematykiem i instruktorem. Wierzę, że oprócz udowodnienia tych rzeczy, duży stół taki jak ten łatwo i znacznie zwiększa intuicję ludzi. A nazwy klas asymptotycznych pomagają ludziom dużo pamiętać i komunikować się.
Apass.Jack
1
@ Apass.Jack Z mojego doświadczenia pedagogicznego, gdy podaje się tabelę, wielu uczniów uczy się na pamięć i nie zamawia żadnych funkcji, których nie ma w tabeli. Zwróć uwagę, jak ten efekt wydaje się odpowiadać na wiele pytań dotyczących asymptotycznego wzrostu, które pojawiają się na tej stronie. To powiedziawszy, oczywiście użyjemy lematów sugerowanych przez tabelę, jeśli ułatwi to proofy, ale pojawia się to po nauce dowodzenia tabeli. (Aby podkreślić tę kwestię, ludzie, którzy tu przychodzą , nie potrzebują pomocy w odczytywaniu rzeczy ze stołu. Potrzebują pomocy w udowodnieniu relacji.)
Raphael
1
@kelalaka „Tak, Landau bardziej dotyczy określonego rodzaju algorytmu w kryptografii”. - to nawet nie ma sensu. Notacja Landaua jest skrótem do opisu właściwości funkcji matematycznych. Nie ma to nic wspólnego z algorytmami, nie mówiąc już o kryptografii.
Raphael