Co jest nie tak z sumami warunków Landau?

napisałem

$\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

ale mój przyjaciel mówi, że to źle. Z ściągawki TCS wiem, że suma nazywa się również $H_n$ 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ć

$\qquad \displaystyle \sum\limits_{i=1}^n i = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

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

asymptotics landau-notation

— Raphael
źródło

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:

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. $\mathcal{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 , co tak naprawdę mamy na myśli, jeśli to $\mathcal{O}(f)$ $f(n) = g(n) + \mathcal{O}(n)$ $f(n) - g(n) \in \mathcal{O}(n)$ . (Uwaga: niektórzy pedantycy również mogą drżeć z powodu tego stwierdzenia, twierdząc, że jest liczbą $f(n)$ $f$ jest funkcją!)

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

n \leq \sum_{k = 1}^{n} k^{1 / k} \leq n + O (n^{1 / 3})

$n \le \sum_{k=1}^n k^{1/k} \le n + \mathcal{O}(n^{1/3})$

Oznacza to, że istnieje pewna w taki sposób, $f \in \mathcal{O}(n^{1/3})$

n \leq \sum_{k = 1}^{n} k^{1 / k} \leq n + f (n)

$n \le \sum_{k=1}^n k^{1/k} \le n + f(n)$

W twoim przypadku

\sum_{k = 1}^{n} \frac{1}{k} = \sum_{k = 1}^{n} O (1) = O (n)

$\sum_{k=1}^{n} \frac{1}{k} = \sum_{k=1}^{n} \mathcal{O}(1) = \mathcal{O}(n)$

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

Istnieją dwie możliwe interpretacje: Czy odnosi się do funkcji , czy funkcji ? $\mathcal{O}(1)$ $n$ $k$

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 to i próba napisania $n$ $k$ $\mathcal{O}(1)$ $\sum_{k=1}^{n} k = \sum_{k=1}^{n} \mathcal{O}(1)$

Jeśli spróbujesz myśleć o tym jako o funkcji , to prawdą jest, że jeśli (ponieważ argument przechodzi do ) nigdy nie wynosi , to $k$ $f = \mathcal{O}(g)$ $\infty$ $g$ $0$

S (n) = \sum_{k = 1}^{n} f (k) = \sum_{k = 1}^{n} O (g (k)) = O (\sum_{k = 1}^{n} | g (k) |)

$S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(k)) = \mathcal{O}(\sum_{k=1}^{n} |g(k)|)$

Zauważ, że w środku zastosowaliśmy wygodne nadużycie notacji co oznacza, że dla niektórych funkcji suma wynosi . Zauważ, że końcowa funkcja wewnątrz odnosi się do funkcji $\mathcal{O}(g(k))$ $h \in \mathcal{O}(g)$ $\sum_{k=1}^{n} h(k)$ $\mathcal{O}$ $n$ . 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 (jak argument przechodzi do $n$ $f = \mathcal{O}(g)$ ), to $\infty$

S (n) = \sum_{k = 1}^{n} f (k) = \sum_{k = 1}^{n} O (g (n)) = O (n g (n))

$S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(n)) = \mathcal{O}(n g(n))$

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

— Aryabhata
źródło

Konkluzja: Należy pamiętać (upewnić się), że każde wystąpienie symbolu Landau wprowadza (ma) swoją stałą .

— Raphael

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

Dowód: . $\sum_{i=1}^n \frac{1}{i} \le \ln n + 1 \le 2n = O(n)$ $\square$

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

— JeffE
źródło

Dobra: 1 / i ≤ 1 = O (1).

— JeffE

Problem dotyczy drugiego znaku równości. Jak to zweryfikować?

— Raphael

Ale to też jest poprawne. Suma n terminów, z których każdy to O (1), jest rzeczywiście O (n).

— Suresh

@Suresh Tylko wtedy, gdy stałe sugerowane przez

są niezależne od zmiennej sumowania, i to jest tutaj punkt (pytanie o ziarno).

O

$\cal{O}$

— Raphael

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

jest błędne. Zdaję sobie sprawę, że jest to oczywiste dla wszystkich zainteresowanych, ale myślę, że jest to problem z „zadawaniem pytań” :)

\sum_{i} O (1) = O (n)

$\sum_i O(1) = O(n)$

i = O (1)

$i = O(1)$

— Suresh

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

i = O (1)

$i = O(1)$

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

\sum_{ja = 1}^{n} ja = \sum_{ja = 1}^{n} O (n) = n O (n) = O (n^{2)})

$\sum_{i=1}^n i = \sum_{i=1}^n O(n)= nO(n) = O(n^2)$

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