Co jest nie tak z sumami warunków Landau?

14

napisałem

i=1n1i=i=1nO(1)=O(n)

ale mój przyjaciel mówi, że to źle. Z ściągawki TCS wiem, że suma nazywa się również Hn która ma logarytmiczny wzrost w n . Więc moja granica nie jest zbyt ostra, ale wystarcza do analizy, której potrzebowałem.

Co zrobiłem źle?

Edycja : Mój przyjaciel mówi, że z tego samego rozumowania możemy to udowodnić

i=1ni=i=1nO(1)=O(n)

Teraz jest to oczywiście źle! Co tu się dzieje?

Raphael
źródło
2
Zobacz dyskusję na temat tagów tego pytania tutaj .
Raphael
meta dyskusja na temat algorytmów tagów .
Kaveh
Zobacz także bardziej konkretne podejście do wspólnego przykładu: jaki jest asymptotyczny czas działania tej zagnieżdżonej pętli?
Gilles „SO- przestań być zły”

Odpowiedzi:

10

To, co robisz, to bardzo wygodne nadużycie notacji.

Niektórzy pedanci powiedzą, że to, co piszesz, to bzdury, ponieważ oznacza zbiór i nie możesz wykonywać na nich operacji arytmetycznych tak, jak robisz.O(f)

Ale dobrym pomysłem jest zignorowanie tych pedantów i założenie, że oznacza jakiegoś członka zestawu. Kiedy więc mówimy f ( n ) = g ( n ) + O ( n ) , co tak naprawdę mamy na myśli, jeśli to f ( n ) - g ( n ) O ( n )O(f)f(n)=g(n)+O(n)f(n)g(n)O(n) . (Uwaga: niektórzy pedantycy również mogą drżeć z powodu tego stwierdzenia, twierdząc, że jest liczbą iff(n)f jest funkcją!)

To sprawia, że ​​bardzo wygodne jest pisanie takich wyrażeń jak

nk=1nk1/kn+O(n1/3)

Oznacza to, że istnieje pewna w taki sposób,fO(n1/3)

nk=1nk1/kn+f(n)

W twoim przypadku

k=1n1k=k=1nO(1)=O(n)

nadużywasz go jeszcze bardziej i musisz być ostrożny.

Istnieją dwie możliwe interpretacje: Czy odnosi się do funkcji n , czy funkcji k ?O(1)nk

Uważam, że właściwą interpretacją jest interpretacja jej jako funkcji .k

Jeśli spróbujesz myśleć o tym jako o funkcji , uważanej za niepoprawną, może to prowadzić do potencjalnych błędów, takich jak myślenie, że k to O ( 1 ) i próba napisania n k = 1 k = n k = 1 O ( 1 )nkO(1)k=1nk=k=1nO(1)

Jeśli spróbujesz myśleć o tym jako o funkcji , to prawdą jest, że jeśli f = O ( g ) (ponieważ argument przechodzi do ) ig nigdy nie wynosi 0 , tokf=O(g)g0

S(n)=k=1nf(k)=k=1nO(g(k))=O(k=1n|g(k)|)

Zauważ, że w środku zastosowaliśmy wygodne nadużycie notacji co oznacza, że ​​dla niektórych funkcji h O ( g ) suma wynosi n k = 1 h ( k ) . Zauważ, że końcowa funkcja wewnątrz O odnosi się do funkcji nO(g(k))hO(g)k=1nh(k)On . Dowód nie jest taki trudny, ale musisz się zadowolić faktem, że masz do czynienia z asymptotyczną górną granicą (tj. Dla wystarczająco dużych argumentów), ale suma zaczyna się od .1

Jeśli spróbujesz myśleć o tym jako o funkcji , to jest również prawdą, że jeśli f = O ( g ) (jak argument przechodzi donf=O(g) ), to

S(n)=k=1nf(k)=k=1nO(g(n))=O(ng(n))

Zatem twój dowód jest zasadniczo poprawny, w obu interpretacjach.

Aryabhata
źródło
1
Konkluzja: Należy pamiętać (upewnić się), że każde wystąpienie symbolu Landau wprowadza (ma) swoją stałą .
Raphael
8

To, co napisałeś, jest całkowicie poprawne. p harmonicznej jest rzeczywiście w zbiorze O ( Nn .O(n)

Dowód: .i=1n1ilnn+12n=O(n)

Górna granica nie jest ciasna , ale jest poprawna.O(n)

JeffE
źródło
4
Dobra: 1 / i ≤ 1 = O (1).
JeffE
1
Problem dotyczy drugiego znaku równości. Jak to zweryfikować?
Raphael
2
Ale to też jest poprawne. Suma n terminów, z których każdy to O (1), jest rzeczywiście O (n).
Suresh
2
@Suresh Tylko wtedy, gdy stałe sugerowane przez są niezależne od zmiennej sumowania, i to jest tutaj punkt (pytanie o ziarno). O
Raphael
2
Błąd nie dotyczy drugiej równości. błąd (w drugim wyrażeniu) polega na tym, jak DOSTAJESZ do tego podsumowania. Przejście z jest poprawne. Twierdzi, że i = O ( 1 ) jest błędne. Zdaję sobie sprawę, że jest to oczywiste dla wszystkich zainteresowanych, ale myślę, że jest to problem z „zadawaniem pytań” :)iO(1)=O(n)i=O(1)
Suresh
6

W drugim przykładzie nie można twierdzić, że

i=O(1)

ponieważ różni się n . Po kilku krokach będzie tak, że i > n / 2 . Bardziej właściwy sposób można powiedzieć, że I = O ( n ) , ponieważ w rzeczywistości, przez sumowanie i nigdy nie przekracza 1 n . Zgodnie z tym rozumowaniem n i = 1 i = n i = 1 O ( n ) = n O ( n ) = O (inja>n/2)ja=O(n)ja1n

ja=1nja=ja=1nO(n)=nO(n)=O(n2))

Jednak właściwą rzeczą jest użycie notacji Big-O tylko na końcu. Górna granica podsumowania jest tak ciasna, jak to tylko możliwe, i tylko wtedy, gdy skończysz, użyj asymptotycznych notacji, aby uniknąć tych pułapek.

Ran G.
źródło