szukanie zaawansowane
 [ Posty: 9 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 31 paź 2011, o 19:49 
Użytkownik

Posty: 75
Lokalizacja: Nowy Sącz
Mam oszacować następujące wyrażenie:
f(n)=(1+\frac{1}{n})^n

Definicja notacji O:
Mówimy, że f(n)=O(g(n)), jeżeli możemy wskazać dwie dodanie liczby n_0 oraz c takie, że:
0 \le f(n)  \le c g(n)
dla dowolnego n  \ge n_0.

Zapisałem więc:
(1) 0  \le (1+\frac{1}{n})^n  \le c (1+\frac{1}{n})^n
Mogę podzielić przez wartość w nawiasie, ponieważ jest zawsze większa od 0.
0  \le 1  \le c

Wybrałem n_0 = 1 oraz c = 11.

Wstawiam do (1), w zasadzie mogę zapisać:
1 \le 11
Jest to prawda. Pytanie jak się to fachowi robi. I czy o to chodzi?
Góra
Mężczyzna Offline
PostNapisane: 31 paź 2011, o 20:01 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
To prawda, że \left(1+\frac1n\right)^n=O\left(\left(1+\frac1n\right)^n\right), ale lepszym szacowaniem jest \left(1+\frac1n\right)^n=O(1), co znaczy tyle że \left(1+\frac1n\right)^n jest ciągiem ograniczonym.
Góra
Mężczyzna Offline
PostNapisane: 31 paź 2011, o 20:35 
Użytkownik

Posty: 75
Lokalizacja: Nowy Sącz
Okay, czyli zawsze jak mam ciąg ograniczony to O(1). Ciąg ten w nieskończoności dąży do e.

Już zapomniałem wiele z tej najbardziej podstawowej analizy, ale czy ciąg jest ograniczony zawsze wtedy, gdy posiada granicę właściwą, przy n \to \infty, czy potrzeba sprawdzać coś jeszcze?
Góra
Mężczyzna Offline
PostNapisane: 31 paź 2011, o 20:42 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Gdy ma granicę właściwą to jest ograniczony.
Góra
Mężczyzna Offline
PostNapisane: 31 paź 2011, o 20:57 
Użytkownik

Posty: 75
Lokalizacja: Nowy Sącz
Okay. A wezmę teraz taką funkcję:
f(n)=n+\lg(n)

Korzystając z tej samej definicji, napiszę że:
0 \le n + lgn  \le cn
Prawda dla c = 1\\ n_0 = 1.

Wniosek:
O(n+lgn)=O(n)
Czyli jest to złożoność liniowa.

Zgadza się?
Góra
Mężczyzna Offline
PostNapisane: 31 paź 2011, o 21:47 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Nie możesz wziąć c=1, bo nieprawda że n+\lg n\le n, ale masz rację, że n+\lg n=O(n).
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2011, o 00:27 
Użytkownik

Posty: 75
Lokalizacja: Nowy Sącz
Dzięki, niedopatrzenie. :oops:

Teraz walczę z taką funkcją:
f(n)=\frac{lgn}{\sqrt[n]{n}}
Zapisałem ją jako:
f(n)=-lgn

Jest to funkcja, która maleje. Raczej nie dam rady oszacować jej za pomocą notacji O. Mogę natomiast spróbować oszacować ją od dołu, stosując notację \Omega.

Jej definicja jest następująca:
Mówimy, że \Omega(g(n)) = f(n) jeżeli istnieją dodatnie stałe c i n_0 takie, że 0  \le c g(n)  \le f(n) dla wszystkich n  \ge n_0.

Postępuje więc analogicznie jak w notacji O.

0  \le -c lg n  \le -lg n
dla c = 1\\ n_0=2
f(n) = \Omega(lgn)
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2011, o 00:34 
Użytkownik
Avatar użytkownika

Posty: 640
Lokalizacja: Bydgoszcz / Warszawa
\frac{\ln n}{\sqrt[n]{n}} nie jest tą samą funkcją co -\ln n. Natomiast prawdziwe są nierówności 1 \le \sqrt[n]{n} \le 2.
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2011, o 00:42 
Użytkownik

Posty: 75
Lokalizacja: Nowy Sącz
EDIT: już widzę błąd.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 9 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 zad z symbolu newtona  Anonymous  1
 Symbolu sumy i iloczynu - podstawy.  Kamlor  2
 Zapisz bez uzywania symbolu silni i uprosc ulamek  nice88  6
 Silnia-oblicz wartość wyrażenia  deftfan  2
 Udowodnij wlasność symbolu Newtona  ag17  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl