(przykład)
Sprawozdanie – AISDE
LAB 1 - Złożoność
(by Zanlik)
1. Sformułowanie zadania
Zakodować algorytm liczenia (dla 50 próbek) N- średnia liczba dodatnich liczb w ciągu elementowym. Elementami ciągu są liczby całkowite należące do przedziału [-M,M].
Zbadać złożoność obliczeniową algorytmu (dla n=6:6:60, operację dominującą przyjąć porównanie). Czy złożoność zależy od wartości M ?
Wyniki przedstawić w postaci graficznej: na jednym wykresie dla 1 próbki (n,z(n)) gdzie z(n) złożoność w zależności od rozmiaru n ; na drugim (n,N(n)) gdzie N(n) średnia liczba Donatich liczb w zależności od rozmiaru n.
2. Opis danych testowych potrzebnych do wykonania zadania
Do wykonania zadania potrzebne będzie stworzenie ciągu o długości n. Elementami ciągu są liczby całkowite generowane przez funkcje round i rand w przedziale [-M,M].
Do eksperymentalnego sprawdzenia złożoności potrzebny będzie licznik, który będzie zliczał
operacje dominujące.
3. Opis wyników jakich należy się spodziewać na podstawie teorii
Przyjęto porównanie jako operację dominującą więc złożoność tego algorytmu nie będzie zależała od wartości danych (przedziału [-M,M]) lecz od wielkości danych. Można się spodziewać liniowej złożoności, gdyż liczba operacji dominujących wykonanych w trakcie algorytmu (porównań) jest równa długości ciągu.
4. Graficznie przedstawienie wyników eksperymentalnych i teoretycznych Zlozonosc obliczeniowa w zaleznosci od rozmiaru danych 60
h 50
cycjau 40
inmo
ji d 30
craep 20
oabzic 10
L
00
10
20
30
40
50
60
Rozmiar ciagu
Srednia liczba dodatnich liczb w ciagu (dla 50 próbek) w zaleznosci od rozmiaru ciagu 30
b 25
z
lichic 20
tnado d 15
abz
lic 10
iandre 5
S
00
10
20
30
40
50
60
Rozmiar ciagu
5. Omówienie otrzymanych wyników
Na wykresach wyraźnie widać, że złożoność obliczeniowa algorytmu jest liniowa. W kodzie algorytmu umieszczono licznik, który zlicza ilość porównań w czasie wykonywania algorytmu.
Znajduje się on w pętli for czyli licznik przyjmie taką wartość jaki ma rozmiar pętla, co tłumaczy otrzymany wynik.
Złożoność nie zależy on wartości danych ponieważ porównanie zostanie wykonane dla każdej liczby (dodatnie i ujemne).
Widzimy na drugim wykresie, że średnia liczba dodatnich liczb w ciągu jest w przybliżeniu równa połowie rozmiaru ciągu, czyli tyle ile wynosi prawdopodobieństwo znalezienia dodatniej liczby w ciągu. (oczywiście dla symetrycznego przedziału [-M,M])
6. Wnioski
Dla danego w ćwiczeniu algorytmu złożoność czasowa pesymistyczna i optymistyczna są takie same czyli W(n)=B(n)=n, gdyż złożoność nie zależy od wartości danych.
(Nie wiem co jeszcze napisać)