Średnia złożoność obliczeniowa algorytmu

lady_k8 · Post autor: **lady_k8** » 16 lis 2009, o 11:35

Hej

Nie wiem czy to odpowiedni dział, więc z góry przepraszam

Mam za zadanie policzyć średnią złożoność obliczeniową algorytmu. Z policzeniem złożoności optymistycznej i pesymistycznej nie miałam problemu, ale przy średniej zaczynają się schody.
Złożoność optymistyczna wyszła stała (konkretnie 1), a złożoność pesymistyczna - kwadratowa.

Jak w takim przypadku policzyć złożoność średnią?

Z góry dzięki
Pozdrawiam
K8

natkoza · Post autor: **natkoza** » 16 lis 2009, o 12:38

zależy w sumie jaki to algorytm

lady_k8 · Post autor: **lady_k8** » 16 lis 2009, o 14:22

Algorytm sprawdza, czy dwie tablice (o takiej samej liczbie elementów) mają wspólną liczbę, a wygląda dość prosto - 2 pętle, a wewnątrz warunek: jeśli t1=t2[j] to zakończ algorytm i zwróć wartość true.

Pozdrawiam
K8

paladin · Post autor: **paladin** » 16 lis 2009, o 16:27

Żeby policzyć złożoność średnią algorytmu, musisz wiedzieć, jak losowane są liczby do tablic. Dlatego nazywa się "średnia" - musi być średnią po czymś

A swoją drogą, pojęcie złożoności optymistycznej jest nieco dziwne, nigdy nie spotkałem się, żeby ktoś liczył to na poważnie.

lady_k8 · Post autor: **lady_k8** » 17 lis 2009, o 19:58

paladin pisze:Żeby policzyć złożoność średnią algorytmu, musisz wiedzieć, jak losowane są liczby do tablic. Dlatego nazywa się "średnia" - musi być średnią po czymś

Nie mam żadnych danych, żadnych innych informacji poza sposobem działania algorytmu, więc jak mogę policzyć po "czymś"?

Na wykładzie profesor mówił, że w przypadku obu złożoności tego samego rzędu można policzyć średnią złożoność jako średnią arytmetyczną, ale co w przypadku złożoności różnego rzędu?

paladin · Post autor: **paladin** » 17 lis 2009, o 21:44

Chodzi o to, że złożoność będzie inna, jeśli n jest małe, a liczby losowane z bardzo dużego przedziału, a inna jeśli liczby są zerami lub jedynkami. "Średnia złożoność" nie oznacza "średnia z dwóch różnych algorytmów". Oznacza "jeśli programowi damy wszystkie możliwe zestawy danych, ile typowo zajmie mu działanie?"
Bez żadnych informacji, jakie są możliwe zestawy danych (w sensie: jaki jest zasięg liczb w tablicach) nie da się zrobić tego zadania.

lady_k8 · Post autor: **lady_k8** » 17 lis 2009, o 23:58

paladin pisze:Chodzi o to, że złożoność będzie inna, jeśli n jest małe, a liczby losowane z bardzo dużego przedziału, a inna jeśli liczby są zerami lub jedynkami. "Średnia złożoność" nie oznacza "średnia z dwóch różnych algorytmów". Oznacza "jeśli programowi damy wszystkie możliwe zestawy danych, ile typowo zajmie mu działanie?"
Bez żadnych informacji, jakie są możliwe zestawy danych (w sensie: jaki jest zasięg liczb w tablicach) nie da się zrobić tego zadania.

Wydaje mi się, że nie do końca się rozumiemy. Jakie dwa różne algorytmy masz na myśli?

Załóżmy, że mam 2 tablice, każda ma po 5 (n) elementów. Operacją dominującą (czyli de facto decydującą o złożoności) w algorytmie jest porównanie.
W przypadku optymistycznym na pierwszych pozycjach obu tabel jest taka sama liczba, więc liczba porównań jest równa 1.
W przypadku pesymistycznym taka sama liczba jest na ostatnich pozycjach obu tabel, albo wręcz nie ma takiej samej liczby - wtedy liczba porównań wynosi n*n, czyli 25.
Jak teraz policzyć średnią?

Pozdrawiam
K8

paladin · Post autor: **paladin** » 18 lis 2009, o 00:09

Średnia złożoność nie zależy od optymistycznej (wspominałem, że to bezsensowne pojęcie?) i pesymistycznej.

Hm, może u Ciebie jest inna definicja średniej złożoności...możesz ją przytoczyć?

lady_k8 · Post autor: **lady_k8** » 18 lis 2009, o 09:39

Jak już wspomniałam prowadzący na wykładzie mówił, że w przypadku gdy obie złożoności są tego samego rzędu, to można policzyć średnią arytmetyczną popełniając przy tym błąd obliczeń na poziomie pojedynczej operacji. Niestety nie raczył powiedzieć jak to zrobić z różnymi...

Pozdrawiam
K8

paladin · Post autor: **paladin** » 18 lis 2009, o 09:56

Ale samej definicji średniej złożoności nie masz podanej? Bo to na ogół nie jest średnia arytmetyczna...
No to nie masz wyboru: załóż, że liczby w tablicach są losowane z przedziału [0, K]. Jakie masz szanse zakończyć algorytm w danym, ustalonym kroku?

lady_k8 · Post autor: **lady_k8** » 18 lis 2009, o 12:37

Mam tylko taką definicję:
\(\displaystyle{ T _{s}(n) = \sum_{d \in D}^{} p(d) \cdot T(d)}\)
gdzie:
- D - zbiór danych wejściowych
- p(d) - prawdopodobieństwo wystąpienia danej d
- T(d) - złożoność obliczeniowa dla danej d

Pozdrawiam
K8

paladin · Post autor: **paladin** » 18 lis 2009, o 18:18

lady_k8 pisze: - p(d) - prawdopodobieństwo wystąpienia danej d

No właśnie tego potrzeba - skąd wiedzieć, jakie jest prawdopodobieństwo wystąpienia danego zestawu liczb w tablicach?
Rozwiążmy to zadanie przy dość rozsądnym założeniu, że liczby do tablic losowane są jednostajnie z przedziału \(\displaystyle{ [0, K-1]}\). Skorzystam też z nieco innej postaci wzoru na średnią złożoność - jest to wartość oczekiwana liczby kroków, jaką wykona algorytm.

Algorytm wykonuje kolejno \(\displaystyle{ N^2}\) porównań:

\(\displaystyle{ (a_1, b_1)}\)
\(\displaystyle{ (a_1, b_2)}\)
...
\(\displaystyle{ (a_n, b_n)}\)

Szansa, że jedno porównanie zakończy algorytm wynosi \(\displaystyle{ p = 1/K}\), nieudanie się poprzednich porównań nie wpływa na szansę udania następnego. Czyli algorytm z prawdopodobieństwem \(\displaystyle{ p}\) wykona 1 krok, z prawdopodobieństwem \(\displaystyle{ (1-p) p}\) 2 kroki, z prawdopodobieństwem \(\displaystyle{ (1-p)^2 p}\) 3 kroki itd. Z prawdopodobieństwem \(\displaystyle{ (1-p)^{n^2}}\) przejdzie wszystkie liczby i nie znajdzie żadnej równości.

Pozostaje policzyć wartość oczekiwaną:

\(\displaystyle{ \sum_{j=1}^{n^2} j \cdot p \cdot (1-p)^{j-1} + (1-p)^{n^2} \cdot n^2 = \ldots}\)

Obawiam się, że to dość brzydka suma. Wychodzi coś rzędu \(\displaystyle{ n^2(1-1/K)^{n^2 - 1}}\)

lady_k8 · Post autor: **lady_k8** » 19 lis 2009, o 09:12

Hmm, miałam nadzieję, że da się to policzyć prościej Niemniej wielkie dzięki za pomoc.

Pozdrawiam
K8