Algorytmy i struktury danych · Laboratorium 2

Złożoność i wydajność

Celem jest przewidywanie wzrostu kosztu algorytmu przed pomiarem oraz sprawdzanie, czy dane empiryczne są zgodne z analizą.

1. Model kosztu

Ustal rozmiar wejścia n i operację dominującą. Policz jej wykonania zamiast czasu zależnego od komputera.

dla i od 0 do n - 1:
  dla j od 0 do i:
    wykonaj operację
Zadanie 1. Zapisz sumę liczby operacji, uprość ją i podaj ścisłe oszacowanie asymptotyczne. Sprawdź wynik ręcznie dla n = 1, 2, 3, 4.

2. Granice asymptotyczne

NotacjaZnaczenie
O(g(n))asymptotyczna granica górna
Ω(g(n))asymptotyczna granica dolna
Θ(g(n))jednocześnie granica górna i dolna

Jeżeli koszt wynosi 3n² + 5n + 8, to należy do Θ(n²). Stałe i składniki niższego rzędu nie zmieniają tempa wzrostu, lecz mogą mieć znaczenie dla małych danych.

Zadanie 2. Uporządkuj funkcje 1, log₂n, n, n log₂n, n² i 2ⁿ. Następnie oblicz ich wartości dla n = 16 i n = 1024.

3. Czas i pamięć

Przeanalizuj dwie implementacje wykrywania duplikatu: porównanie każdej pary oraz zapis napotkanych wartości w zbiorze. Dla obu metod podaj koszt czasowy i dodatkową pamięć w najgorszym przypadku.

Zadanie 3. Wyjaśnij, kiedy większe zużycie pamięci jest uzasadnioną ceną za krótszy czas. Uwzględnij ograniczenia wejścia i środowiska.

4. Eksperyment

Zaimplementuj obie metody. Oddziel przygotowanie danych od mierzonego fragmentu. Dla każdego rozmiaru wykonaj kilka powtórzeń za pomocą timeit.repeat i zapisz minimum oraz medianę.

from timeit import repeat
wyniki = repeat("funkcja(dane)", setup="from __main__ import funkcja, dane",
                 repeat=7, number=100)
Zadanie 4. Zbadaj co najmniej sześć rozmiarów wejścia. Na wykresie pokaż czas względem n. Wskaż zakres, w którym koszty stałe zakłócają przewidywany trend.

5. Sprawozdanie

  1. Model kosztu i wyprowadzenie liczby operacji.
  2. Klasy złożoności czasu i pamięci obu metod.
  3. Opis środowiska, dane wejściowe i procedura pomiaru.
  4. Tabela wyników, wykres oraz porównanie z analizą.
  5. Wnioski i ograniczenia eksperymentu.
  6. Zakres użycia AI albo informacja, że AI nie użyto.

Przykład opisu AI: „Użyłem modelu GPT-5 do kontroli rozumowania po promptcie: «Sprawdź, czy poprawnie wyprowadziłem liczbę wykonań operacji w tej pętli. Wskaż pierwszy błędny krok, bez podawania gotowego wyniku». Po wskazaniu błędu samodzielnie przeliczyłem sumę i zweryfikowałem ją dla czterech małych wartości n.”

Źródła

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest i C. Stein, Introduction to Algorithms, wyd. 4, MIT Press, 2022.
  2. A. Levitin, Introduction to the Design and Analysis of Algorithms, wyd. 3, Pearson, 2022.
  3. Python: dokumentacja modułu timeit.