Szeregowanie funkcji złożoności obliczeniowej algorytmów

0

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).

1

Licz granice wszystkich możliwych ułamków, np. \lim_{n \to \infty},\frac{2^n}{log(n)}

0

Bez podania zakresu n -> zadanie jest nawet bez sensu.

0

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.

0

@Wibowit, Na ten temat klucz się z Cormen'em. Jak go przekonasz to porozmawiamy.

0

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

0

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.

0

Tak. Najpierw uszereguj na intuicję, a potem sprawdź matematycznie poprawność uszeregowania.

1 użytkowników online, w tym zalogowanych: 0, gości: 1