Witam, zastanawiam się w jaki sposób zabrać się do takiego zadanka:
Uszereguj malejąco funkcje złożoności obliczeniowej algorytmów:
O(2n), O(logn), O(n!), O(n(1/3)), O(n), O(n(3/2)), O(nlogn), 0(10logn), O(l/n).
Witam, zastanawiam się w jaki sposób zabrać się do takiego zadanka:
Uszereguj malejąco funkcje złożoności obliczeniowej algorytmów:
O(2n), O(logn), O(n!), O(n(1/3)), O(n), O(n(3/2)), O(nlogn), 0(10logn), O(l/n).
Licz granice wszystkich możliwych ułamków, np.
Bez podania zakresu n -> zadanie jest nawet bez sensu.
Ma sens. n domyślnie dąży do nieskończoności. To jest przecież złożoność asymptotyczna. A więc ustalony porządek ma być prawidłowy dla każdego n >= N, gdzie N jest konkretną stałą zależną od tego porządku.
Mam Cormena od liceum. Możesz podać miejsce które masz na myśli.
O(cośtam) jest zbiorem funkcji rzędu co najwyżej (cośtam). Wydaje mi się że dla każdej pary zbiorów O(cośtam1) i O(cośtam2) albo pierwszy zawiera się w drugim, albo drugi zawiera się w pierwszym, albo są równe. Nie mogę znaleźć na to jednak wprost potwierdzenia.
Edit:
Chociaż w sumie dla dziwnych kategorii funkcji może być inaczej. W każdym razie funkcje z zadania wyglądają w miarę "normalnie" i można je potraktować limesami tak jak bogdans zasugerował, albo np gość tutaj: http://stackoverflow.com/a/9545502/492749
Dziękuję za odpowiedzi. W przypadku takiego zadania na egzaminie najrozsądniej będzie liczyć te granice i cały czas je szeregować, aby nie musieć liczyć wszystkich możliwości.
Tak. Najpierw uszereguj na intuicję, a potem sprawdź matematycznie poprawność uszeregowania.