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

Odpowiedz Nowy wątek
2014-06-07 17:38
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).

edytowany 1x, ostatnio: bryla33, 2014-06-07 17:42

Pozostało 580 znaków

2014-06-07 18:07

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


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 2x, ostatnio: bogdans, 2014-06-07 18:10

Pozostało 580 znaków

2014-06-07 18:13
0

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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-06-07 18:18
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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2014-06-07 18:25
0

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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-06-07 18:37
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


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2014-06-07 18:44

Pozostało 580 znaków

2014-06-08 08:44
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.

Pozostało 580 znaków

2014-06-08 11:50
0

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


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
Na intuicję wygrywa ostatni z zadania - O(1/n). Ogłaszam konkurs na realnie działający algorytm z taką złożonością. - bogdans 2014-06-08 12:41

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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