[SzCzoteckY]

dwa algorytmy rozwiązujące ten sam problem
1. klasy O(n)
2. klasy o(n)
- Który doprowadzi do rozwiązania problemu szybciej na dowolnym komputerze?
- Który bedzie lepszy dla bardzo dużych rozmiarów danych?
i dlaczego tak a nie inaczej?

#programowanie #informatyka #strukturydanych

[v.....d]

@SzCzoteckY: https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu
moim zdaniem małe o, bo zakłada, że algorytm ma złożoność mniejszą od n
choć w sumie dwa pytania i taka sama odpowiedź, może jednak coś nie pasuje, niech się inni wypowiedzą

[ponton]

@SzCzoteckY: Pytanie nie ma sensu, bo funkcja stała f(n) = 1 też jest O(n), a nawet O(n^2) czy O(2^n). Duże (i małe) O to tylko ograniczenie górne.

Natomiast jeśli powiedziane jest, że pierwszy algorytm, który jest klasy O(n), nie jest o(n), to znaczy, że ten drugi będzie szybszy.

[SzCzoteckY]

@ponton: pytanie ma sens uwierz :)

@variableisnotinitialized: na moje oko jest tak samo bo:
O(n) zakłada ze operacji bedzie <= n
o(n) zakłada ze operacji bedzie < n

więc:
dla takiego samego problemu na dowolnym komputerze rozwiazanie bedzie szybsze w przypadku użycia o(n) choć mogą zdarzyć się przypadki kiedy ten czas bedzie taki sam

dla duzej ilosci danych zdecydowanie lepiej wypada o(n) bo zakłada, ze operacji nawet w przypadku pesymistycznym

[ponton]

@SzCzoteckY: To tak jakbym powiedział, że mamy dwie liczby:

1. Jest mniejsza od 100.
2. Jest mniejsza od 200.

Która jest większa? Nie wiadomo. Mogą to być liczby 20 (mniejsza od 100) i 10 (mniejsza od 200) i wtedy pierwsza będzie większa. Duże O to tylko ograniczenie górne. Gdyby tam była ϴ, zamiast O, to byłoby jasne.

[SzCzoteckY]

@ponton: ale jest zaznaczone ze rozwiązują ten sam problem

[ponton]

@SzCzoteckY: Ok, dam przykład. Masz quick sort i bubble sort. Oba algorytmy rozwiązują ten sam problem.

Fakt 1. Quick sort jest O(n^3),
Fakt 2. Bubble sort jest o(n^3).

Fakt 3. Quick sort jest szybszy, bo jest też O(n*log n), podczas gdy buble sort nie jest O(n log n).

Gdyby patrzeć tylko na o i O, to by wychodziło, że bubble sort jest szybszy.

[SzCzoteckY]

@ponton: czekaj sorka bo nie rozumiem troche jak QuickSort moze byc jednoczesnie O(n^3) i O(n logn) ???

[fnord23]

@SzCzoteckY:
https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu
Podstaw sobie do definicji i sprawdź czy się zgadza.

[Trytka]

@SzCzoteckY: O(n) - daje funkcje ktorej zlozonosc nie przekroczy. To z jaka "dokladnosci" to napiszesz to juz inna sprawa.
Dlatego przejscie po tablicy jest O(n) <= O(n^3) <= O(n^7) itd...