Struktury danych i złożoność obliczeniowa - Klasy O(n) i o(n)

pytanie zadane 4 września 2016 w C i C++ przez LifesGood Nowicjusz (120 p.)

Witam. Czy ktoś jest w stanie pomóc mi z tym zadaniem?

2	komentarz 4 września 2016 przez Kornelia Kobiela Nałogowiec (33,340 p.) Nie rozwiązujemy gotowców.

komentarz 4 września 2016 przez MetRiko Nałogowiec (37,110 p.)

Może się nie znam.. ale dla mnie to wygląda jakby to były te same złożoności obliczeniowe.
Tylko wielkość litery jest różna by podkreślić, żeby można było je rozróżnić. Ale możliwe, że się mylę.

komentarz 4 września 2016 przez LifesGood Nowicjusz (120 p.)

To na pewno nie są te same złożoności.

komentarz 4 września 2016 przez MetRiko Nałogowiec (37,110 p.)

Może brakuje czegoś jeszcze.. np. pseudokodu tych algorytmów.

1	komentarz 4 września 2016 przez Eryk Andrzejewski Mędrzec (164,260 p.) https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu#Notacja_.E2.80.9Ema.C5.82e_o.E2.80.9D Może to w czymś pomoże.

komentarz 4 września 2016 przez Eryk Andrzejewski Mędrzec (164,260 p.)

Jeśli dobrze zrozumiałem, to małe o to granica dolna, czyli minimum (optymistyczny przypadek), natomiast duże o to granica górna, czyli maskimum (pesymistyczny przypadek). Dlatego O(n) powinien być szybszy.

komentarz 4 września 2016 przez adrian17 Ekspert (344,860 p.)

Nie.

http://i.stack.imgur.com/SZ7jy.png

Ale osobiście twierdzę że treść pytania jest dziwna, więc nie mogę odpowiedzieć.

2	komentarz 4 września 2016 przez jpacanowski VIP (101,940 p.) Nie rozwiązujemy gotowców. "Pomóc", a nie rozwiązać...

1 odpowiedź

odpowiedź 4 września 2016 przez Thomas Frost Bywalec (2,540 p.)

Cześć,

Tutaj pomoże trochę wikipedia: https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu

O(n) - to znaczy, że nasz algorytm jest co najwyżej rzędu n. To wygląda tak, że mnożymy jakąś funkcję przez pewną stałą i biegnie ona pod funkcją opisującą nasz algorytm, z tym, że jest to bardzo chaotycznie, raz może być bliżej naszej funkcji algorytmicznej, raz wyżej, a raz może ją nawet przeciąć!
o(n) - to znaczy, że nasz algorytm jest niższego rzędu niż n. To wygląda tak jak wyżej, z tym, że mamy dowolną ilość tych stałych i żadna z nich nie jest w stanie przebić się przez naszą funkcję algorytmiczną.

Myślę, że to wystarczy, żebyś był w stanie rozwiązać to zadanie!

Pozdrawiam,
Tomek