Złożoność obliczeniowa algorytmów jest określona przez te 4 funkcje, Proszę uszeregować te funkcje w kolejności wzrastającej złożoności (w sensie notacji duże O). Dla różnych n widać, że kolejność jest inna:
ale, że chodzi o notację duże O to trzeba to zrobić dla n dążącego do nieskończoności, a więc:
i widać tutaj, że wszystkie dążą do nieskończoności (mają inne tempo wzrostu), więc na podstawie czego ja mam to uszeregować?
0
0
Spójrz na samą definicję notacji O, zwróć uwagę na, istnieje dostatecznie duża liczba "n". Coś w ten deseń. Ogólnie widać, że nie czujesz czym to jest i jaki problem ma rozwiązać.
To co sobie wylistowałeś fajnie pokazuje, że stała c też ma znaczenie tj. inaczej sortujesz malutki zbiór liczb, a inaczej większy, mimo iż złożoność na to nie wskazuje
2
i widać tutaj, że wszystkie dążą do nieskończoności (mają inne tempo wzrostu), więc na podstawie czego ja mam to uszeregować?
Dlatego lepiej niż porównywać dla dwóch punktów porównać dla 1000 punktów i zrobić wykres w excelu. Wtedy byś widział iż jest punkt w którym się wykresy rozmijają. Z drugiej strony ten punkt jest na tyle wcześnie iż dla n = 100 bedziesz mieć dobre wartosci
2
@tkowal Zbadaj iloraz F(n) / G(n) dla n -> inf.
np. F(n) = log(n), G(n)=log^2(n)
F(n)/G(n) = log(n) / [ log(n) * log(n) ] = 1/log(n)
Jak się taki iloraz zachowuje w nieskończoności? Która funkcja dominuje ?
0
Wykres z GPT czatu
Widać iż ostateczna kolejność ustala się dla x > 100.
UPDATE chociaż teraz się zastanawiam czy czerwony się kiedyś z pomarańczowym nie przetnie, hm
1
KamilAdam napisał(a):
Wykres z GPT czatu
UPDATE chociaż teraz się zastanawiam czy czerwony się kiedyś z pomarańczowym nie przetnie, hm
x = 5503.6646890767236180771371433796619443670447191302214620770370741....
2
Definicja: https://en.wikipedia.org/wiki/Big_O_notation
Czyli musisz liczyć granice, dla przykładu, f: 2log(n) i g: log(n)^2:
2log(n) / log(n)log(n) → 0 gdy n→∞, z czego wynika, że f jest "małe o" od g, czyli rośnie wolniej; albo g jest "duże O" od f czyli rośnie szybciej. Podobnie dowodzisz dla pozostałych funkcji.
1
tkowal napisał(a):
i widać tutaj, że wszystkie dążą do nieskończoności (mają inne tempo wzrostu), więc na podstawie czego ja mam to uszeregować?
Zawsze możesz spróbować sprawdzić czy te nieskończoności są równoliczne. Jeśli nie to szereguj po mocy.
1
jarekr000000 napisał(a):
x = 5503.6646890767236180771371433796619443670447191302214620770370741....
Czyli za mały zakres wziąłem
BTW ja wiem iż to pytanie teoretyczne, ale w rzeczywistym rozwiązaniu może być tak iż wybór elgorytmu zalezy od ilości elementów wejściowych
NP w Sortowanie Hybrydowe to
- quick sourt - gdy n> 9
- sortowanie przez wstawianie gdy n <=9
Może ty tez należałoby podawać przedziałami, albo podawać ostatni przedział dla którego nie zmieniają się wyniki
BTW 2 na AEI POLSL nie rozważaliśmy takich pokręconych funkcji, dostaliśmy świety "szereg" do zapamietania: const, log n, n n log n, n^2, n^3, 2^n, smok (może coś jeszcze było, ale już nie pamiętam. I nas profesor nie katował pytaniami co większe n^(1/2) czy log ^ 2 (n)
1
Masz jeszcze rozwiązanie analityczne, jeśli prowadzącemu zależy na jakimś uzasadnieniu z analizy matematycznej.
Masz 4 funkcje:
- F1: log(n^2) co możesz zapisać jako 2*log(n)
- F2: [log(n)]^2 = log(n) * log(n)
- F3: n^(1/2) = n^0.5
- F4: n*log(n) - co możesz zapisać jako n^0.5 * n^0.5 * log(n)
Patrzysz na granicę ilorazu, tak by określić relację "<" między funkcjami (relację w sensie która funkcja dominuje w nieskończoności)
- F1/F2 = 2/log(n) dąży do 0 przy n inf -> F1 "<" F2
- F3/F4 = n^0.5 / (n^0.5 * n^0.5 * log(n)) = 1/n^0.5 * log(n) dąży do 0 przy n do inf - > F3 "<" F4
- F2 / F3 = log(n)*log(n) / n^0.5 do czego dąży gdy n dąży do inf ?
Tu chyba najszybciej skorzystać z twierdzenia de L'Hospitala i to dwukrotnie.
Pierwszy raz (liczymy pochodna licznika i dzielimy przez pochodną mianownika i liczymy granicę takiego ilorazu):
- Pochodna licznika: 2/n * log(n)
- Pochodna mianownika: 0.5*n^-0.5
2*log(n) /n
--------------- = 4 * log(n) * n^0.5 / n = 4 *log(n) / sqrt(n)
0.5/n^-0.5
Drugi raz:
- Pochodna licznika: 4/n
- Pochodna mianownika: 0.5*n^-0.5
4/n
------------- = 8n^0.5 / n = 8/n^0.5 a to dąży do 0 przy n do inf, więc F2 "<" F3.
0.5n^-0.5
0
jak to policzyć?
@tkowal Te granice do nieskończoności to liczy sie na oko, jak dokładnie zalezy od przypadku zadania.
Minimalistyczny algorytm liczenia na oko. Skreślasz wszystkie stale i mnożniki, zostawiasz tylko rzeczy będace fukcją n. Robisz szybki porżadek, wybierasz "najwiekszy" czynnik.
Porównujesz porównujesz fukcje dla najwiekszego czynnika. Jest z 10 przypadków prakrycznych max, wiec mozna nauczyc sie tych zestawien na pamieć.
Jak porównać która jest nieskończoność jest wieksza na oko: Zamiast, wyprowadzać granice do nie skończoności, mozesz je przez siebie podzielić, z tego co pamietam to analitcznie poprawne. Jeżeli w wyniku dostaniesz 1 to fukcje są równe, Jeżli wieksze od 1 to fukcja dzielna jest wieksza, jeżeli mniejsze od 1 to dzielnik jest wiekszy, np
(lim->oo N) / (lim->oo N) =1 juz (lim->oo N) / (lim->oo N^2) => 0