(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ć)