Big Oh Notation - definicja formalna

Question

Obecnie czytam podręcznik dla mojej klasy Java III. Czytamy o Big-Oh i jestem nieco zdezorientowany jego formalną definicją.

Definicja formalna: "Funkcja f (n) jest rzędu co najwyżej g (n) - czyli f (n) = O (g (n)) - jeśli dodatnia liczba rzeczywista c i dodatnia liczba całkowita N istnieją tak, że f (n) < = cg (n) dla wszystkich n> = N. To znaczy, cg (n) jest górną granicą na f (n), gdy n jest wystarczająco duże. "

OK, to ma sens. Ale trzymaj się, czytaj dalej ... książka dała mi ten przykład:

„W segmencie 9.14, powiedzieliśmy, że algorytm który wykorzystuje 5N + 3 operacje wynosi O (n) możemy teraz pokazać. że 5n + 3 = o (n) za pomocą formalnej definicji Big OH.

Gdy n> = 3 5n + 3 < = 5n + n = 6n. Jeśli zatem pozwolić f (n) = 5n + 3, g (n) = n, c = 6, N = 3, wykazaliśmy, że f (n) < = 6 g (n) dla n> = 3 lub 5n + 3 = O (n). To znaczy, jeśli algorytm thm wymaga czasu wprost proporcjonalnego do 5n + 3, to jest O (n). "

Ok, ten rodzaj ma dla mnie sens. Mówią, że jeśli n = 3 lub więcej, 5n + 3 zajmuje mniej czasu niż gdy n jest mniejszy niż 3 - czyli 5n + n = 6n - prawda? Ma sens, ponieważ jeśli n wynosi 2, 5n + 3 = 13, a 6n = 12, ale gdy n wynosi 3 lub więcej, 5n + 3 zawsze będzie mniejsze lub równe 6n.

Oto, gdzie się mylić. Dają mi Innym przykładem

Przykład 2: „Niech pokazują, że 4n^2 + 50n - 10 = O (N^2) jest łatwo zauważyć. 4n^2 + 50N - 10 < = 4n^2 + 50n dla dowolnego n Ponieważ 50n < = 50n^2 dla n

= 50, 4n^2 + 50n. - 10 < = 4n^2 + 50n^2 = 54N^2 dla n> = 50. Zatem, dla c = 54 i N = 50, wykazaliśmy, że 4n^2 + 50n - 10 = O (n^2). "

To stwierdzenie nie ma sensu: 50N < = 50n^2 dla n> = 50.

nie jest wcale n zamiar dokonać 50N mniej niż 50N^2? Nie tylko większy lub równy 50? Dlaczego wspomnieli o tym, że 50n < = 50n^2? Co to ma wspólnego z problemem?

Również 4n^2 + 50n - 10 < = 4n^2 + 50n^2 = 54n^2 dla n> = 50 będzie prawdziwe bez względu na to, czym jest n.

A jak na świecie liczby wybierające pokazują, że f (n) = O (g (n))?

Answer 1

Należy pamiętać, że szukasz "górnej granicy na f (n), gdy n jest wystarczająco duże." Tak więc, jeśli możesz pokazać, że f (n) jest mniejsze lub równe c g (n) dla wartości n większej niż N, oznacza to, że c g (n) jest górną granicą dla f (n) i f (n) 'złożoność jest zatem O (g (n)).

Podane przykłady mają na celu pokazanie, że dana funkcja f (n) nigdy nie wzrośnie ponad c * g (n) dla dowolnego n> N. Poprzez manipulowanie początkową górną granicą, aby można ją było wyrazić prostszymi słowami (jeśli 4n^2 + 50n to górna granica na f (n), to znaczy 4n^2 + 50n^2, która jest równa 54n^2, która staje się twoją 54 * g (n), gdzie c = 54 i g (n) = n^2), autorzy mogą wykazać, że f (n) jest ograniczone przez c * g (n), który ma złożoność O (g (n)) i dlatego też f (n).

Answer 2

50n <= 50n^2 for n >= 50 

ponieważ jeśli n wynosi 50, to 50n jest takie samo jak n^2, ponieważ 50 * 50 równa się 50^2.

Podstawiając n^2 dla 50n otrzymujemy

n^2 <= 50n^2 for n >= 50 

co jest oczywiste.

Answer 3

Wszystko na temat wybierania numerów jest następujące: Aby było łatwiej. Ponieważ możesz wybrać dowolne numery, które lubisz dla N i c, autor po prostu wybiera coś, co jest najłatwiejsze do zobaczenia. I to właśnie możesz zrobić (podczas pisania egzaminu itp.).

Podczas gdy często można by użyć mniejszego N, rozumowanie stałoby się nieco trudniejsze (często wymagające wcześniejszej wiedzy o analizie - wszyscy nauczyliśmy się wiele lat wcześniej, że x nie rośnie tak szybko jako x^2 ... Ale czy chcesz zapisać dowód analizy?)

Zachowaj prosty, jest wiadomość :-) To jest trochę dziwne, aby przyzwyczaić się do tego na początku.

Answer 4

Prawdopodobnie powodem, dla którego napisano 50n < = 50n^2 dla n> = 50 jest to, że jeśli n jest mniejsze niż 1, to n^2 < n. Oczywiście, jeśli n jest dodatnią liczbą całkowitą, to tak 50n < = 50n^2. W tym przypadku wydaje się, że n przyjmuje się, że jest liczbą całkowitą dodatnią, chociaż formalna definicja, którą podają, nie stanowi tego wprost.

Rozumiem, dlaczego powiedzenie 50n < = 50n^2 dla n> = 50 może wydawać się trochę głupie. Ale to wciąż prawda. Książka nie mówi 50n < = 50n^2 trzyma TYLKO dla n> = 50; to byłoby fałszywe.

Analogicznie, jeśli powiem "wszyscy moi rodzeństwo mówią po angielsku", byłoby to prawdą, mimo że jest wielu ludzi mówiących po angielsku, którzy nie są moimi rodzeństwem.

Jeśli chodzi o dowód, możemy podzielić go na różne oświadczenia.

(1): 4n^2 + 50n - 10 <= 4n^2 + 50n (for all n) 
(2): 4n^2 + 50n <= 4n^2 + 50n^2 (for all n>=50) 
(3): 4n^2 + 50n^2 = 54 n^2 (for all n, including all n>=50) 
(4): Therefore, 4n^2 + 50n - 10 <= 54n^2 for all n>=50 
(5): Therefore, for f(n)=4n^2 + 50n - 10, g(n)=n^2, N=50, and c=54, 
      the statement f(n) <= c g(n) for all n >= N is true 
(6): Therefore, by definition 4n^2 + 50n - 10=O(n^2). 

Powinno być jasne, że każde z tych stwierdzeń jest prawdziwe, albo na własną rękę (1,2,3) lub w wyniku poprzednich wypowiedzi.

Answer 5

Formalna definicja:

• r (n) = O (g (n)) oznacza, że ​​nie istnieje c> 0, a n , że dla dowolnego n> = N F (n) < = C * g (n)
• r (n) = f (g (n)) oznacza dla każdego c> 0 istnieje n , że dla dowolnego n> = n f (n) < = c * g (n)

Jak można zauważyć, są nieco inne :)