Wyższa Szkoła Technologii Informatycznych

Ćwiczenia Algorytmy i struktury danych

ćwiczenia 4

1. Złożoność czasowa algorytmów

Złożoność obliczeniowa stała - O(1)

Algorytm wykonuje stałą ilość operacji dominujących bez względu na rozmiar danych wejściowych. W takim algorytmie czas wykonania jest stały i nie zmienia się przy zmianie liczby przetwarzanych elementów.

Złożoność obliczeniowa liniowa - O(n)

Dla każdej danej algorytm wykonuje stałą ilość operacji dominujących. Czas wykonania jest proporcjonalny do liczby n danych wejściowych. Czas wykonania rośnie liniowo ze wzrostem liczby elementów.

Złożoność obliczeniowa kwadratowa - O(n²)

Algorytm dla każdej danej wykonuje ilość operacji dominujących proporcjonalną do liczby wszystkich przetwarzanych danych. Czas wykonania jest proporcjonalny do kwadratu liczby danych n.

Inne złożoności tego typu O(n³), O(n⁴)... noszą nazwę wielomianowych złożoności obliczeniowych.

Złożoność obliczeniowa logarytmiczna - O(log n)

W algorytmie zadanie rozmiaru n da się sprowadzić do zadania rozmiaru ⁿ/₂. Typowym przykładem jest wyszukiwanie binarne w zbiorze uporządkowanym. Sprawdzenie środkowego elementu pozwala określić, w której z dwóch połówek zbioru może znajdować się poszukiwany element.

Ponieważ uczniowie młodszych klas liceum nie znają pojęcia logarytmu, podajemy jego skróconą definicję:

Zapis log_ax czytamy: logarytm przy podstawie a z liczby x. Wartością jest wykładnik potęgowy y, do którego należy podnieść podstawę logarytmu a, aby otrzymać liczbę logarytmowaną x.

log_ax = y wtedy i tylko wtedy, gdy a^y = x

W określeniu klasy złożoności obliczeniowej nie podajemy podstawy logarytmu, ponieważ logarytmy o różnych podstawach z tej samej wartości różnią się od siebie jedynie iloczynem przez stałą:

Niech
log_ax = y oraz log_bx = cy

Wtedy
a^y = x, oraz b^cy = x

Stąd
a^y = b^cy

(a)^y = (b^c)^y

Zatem
a = b^c oraz log_bx = c log_ax

Ponieważ podstawy a i b są stałe, to i c musi być stałe. Z kolei z definicji notacji Omikron wynika, iż klasa złożoności dwóch funkcji różniących się jedynie iloczynem przez stałą jest taka sama. W informatyce bardzo często stosuje się logarytmy przy podstawie 2.

Przykład :

log₂4 = 2, bo 2² = 4

log₂16 = 4, bo 2⁴ = 16

log₂256 = 8, bo 2⁸ = 256, itd.

Złożoność obliczeniowa liniowo logarytmiczna - O(n log n)

Zadanie rozmiaru n daje się sprowadzić do dwóch podzadań rozmiaru ⁿ/₂ plus pewna ilość operacji, których liczba jest proporcjonalna do ilości danych n. Tego typu złożoność obliczeniową posiadają dobre algorytmy sortujące.

Złożoność obliczeniowa wykładnicza - O(2ⁿ), O(n!)

Złożoność obliczeniową O(2ⁿ) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdego podzbioru n danych wejściowych.

Złożoność obliczeniową O(n!) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdej permutacji n danych wejściowych.

SORTOWANIE ZWARIOWANE

SORTOWANIE PRZEZ WYBÓR

Idea algorytmu sortowania przez wybór jest bardzo prosta. Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. Zatem element najmniejszy powinien znaleźć się na pierwszej pozycji. Szukamy w zbiorze elementu najmniejszego i wymieniamy go z elementem na pierwszej pozycji. W ten sposób element najmniejszy znajdzie się na swojej docelowej pozycji.

W identyczny sposób postępujemy z resztą elementów należących do zbioru. Znów wyszukujemy element najmniejszy i zamieniamy go z elementem na drugiej pozycji. Otrzymamy dwa posortowane elementy. Procedurę kontynuujemy dla pozostałych elementów dotąd, aż wszystkie będą posortowane.

SORTOWANIE BĄBELKOWE

SORTOWANIE BĄBELKOWE WERSJA 2

SORTOWANIE BĄBELKOWE WERSJA 3

SORTOWANIE BĄBELKOWE WERSJA 4

---