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

Szeregowanie funkcji złożoności obliczeniowej algorytmów
B3
  • Rejestracja: dni
  • Ostatnio: dni
  • Postów: 79
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).

bogdans
  • Rejestracja: dni
  • Ostatnio: dni
1

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

_13th_Dragon
  • Rejestracja: dni
  • Ostatnio: dni
0

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

Wibowit
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: XML Hills
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.

_13th_Dragon
  • Rejestracja: dni
  • Ostatnio: dni
0

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

Wibowit
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: XML Hills
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

B3
  • Rejestracja: dni
  • Ostatnio: dni
  • Postów: 79
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.

Wibowit
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: XML Hills
0

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

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.