Złożoność obliczeniowa

Wiesz już, jak możemy zdefiniować złożoność obliczeniową – opisaliśmy to w e‑materiale Złożoność obliczeniowa algorytmówPLbEkkFvZłożoność obliczeniowa algorytmów. Złożoność obliczeniowa algorytmu pozwala określić ilość zasobów komputerowych niezbędnych do wykonania czynności opisanych w algorytmie w zależności od rozmiaru danych wejściowych.

Analiza złożoności obliczeniowej

Analiza złożoności obliczeniowej jest kluczowym narzędziem w pracy programisty pomagającym w wyborze optymalnych algorytmów dla różnych zastosowań.

W innych e‑materiałach przedstawiliśmy różne klasy złożoności obliczeniowej, które można przypisać algorytmom. Porównywanie złożoności obliczeniowej różnych algorytmów pozwala na ocenę ich wydajności. Aby to zrobić, należy zidentyfikować klasę złożoności każdego algorytmu i porównać je względem siebie.

Analiza złożoności obliczeniowej pomaga programistom w wyborze najlepszych algorytmów dla różnych zastosowań, szczególnie w sytuacjach, gdy istotna jest efektywność. Dzięki analizie złożoności obliczeniowej możemy unikać wykorzystywania algorytmów o wysokiej złożoności obliczeniowej w przypadkach, gdy mogą one prowadzić do problemów z wydajnością systemu, zwłaszcza przy dużych zbiorach danych.

Analiza złożoności obliczeniowej pozwala również ocenić, czy proponowane usprawnienia w istniejących algorytmach faktycznie wpłyną na poprawę ich wydajności.

W praktyce analiza złożoności obliczeniowej nie zawsze jest wystarczająca do wyboru najlepszego algorytmu, ponieważ musimy uwzględnić także inne czynniki, np.:

• złożoność pamięciowa,

• ograniczenia sprzętowe.

Analiza złożoności obliczeniowej może być przeprowadzana zarówno teoretycznie, jak i eksperymentalnie. W teoretycznym podejściu badamy algorytm pod kątem liczby operacji, które wykonuje w zależności od wielkości danych wejściowych.

Eksperymentalne podejście polega na przeprowadzaniu testów wydajności, mierząc rzeczywisty czas wykonania algorytmu dla różnych wielkości danych wejściowych.

Dostępne są różne narzędzia i techniki do tego wykorzystywane. W tym e‑materiale zaprezentujemy podejście teoretyczne.

Przykładowe problemy

Sortowanie

W przyszłości poznasz różne algorytmy sortowania. W e‑materiałach opisujemy następujące:

• sortowanie przez wybieraniePT5YE0lsBsortowanie przez wybieranie,

• sortowanie przez wstawianiePJ4y2qWoXsortowanie przez wstawianie,

• sortowanie bąbelkowePCfvfjgLksortowanie bąbelkowe,

• sortowanie kubełkowePPpmzST7zsortowanie kubełkowe,

• sortowanie pozycyjnePjBWIbxmPsortowanie pozycyjne,

• sortowanie przez zliczaniePNx8quWZlsortowanie przez zliczanie,

• sortowanie przez scalaniePNHdnGJ4Isortowanie przez scalanie.

Sortowanie przez wybieranie

Sortowanie przez wybieranie działa na zasadzie wyszukiwania najmniejszego (lub największego) elementu w tablicy i zamiany jego pozycji z pierwszym (lub ostatnim) elementem. Następnie proces jest powtarzany dla pozostałych elementów.

W przypadku sortowania przez wybieranie do czynienia mamy ze złożonością $O(n^2)$.

Sortowanie przez wstawianie

Sortowanie przez wstawianie polega na iteracyjnym wstawianiu elementów do uprzednio posortowanej części tablicy. Algorytm ten przegląda elementy od drugiego do końca tablicy, porównuje je z elementami posortowanymi wcześniej i wstawia je na odpowiednie miejsce.

W przypadku sortowania przez wstawianie do czynienia mamy ze złożonością $O(n^2)$.

Sortowanie bąbelkowe

Sortowanie bąbelkowe działa na zasadzie porównywania sąsiednich elementów w tablicy i zamiany ich miejscami, jeśli są w złej kolejności. Proces ten jest powtarzany, aż do uzyskania posortowanej tablicy.

W przypadku sortowania bąbelkowego do czynienia mamy ze złożonością $O(n^2)$.

Sortowanie kubełkowe

Sortowanie kubełkowe działa przez podział wartości na kilka „kubełków” (przedziałów) i sortowanie ich niezależnie, zwykle za pomocą innego algorytmu sortowania. Po posortowaniu elementów w każdym kubełku są one łączone z powrotem, tworząc posortowaną tablicę.

W przypadku sortowania kubełkowego do czynienia mamy ze złożonością $O(n + k)$ dla przypadków optymistycznego i średniego oraz $O(n^2)$ dla przypadku pesymistycznego.

Nie będziemy analizować kolejnych algorytmów. Na tym etapie możemy zdecydować, że najmniejszą złożoność obliczeniową dla tego przypadku ma algorytm sortowania przez wstawianie.

Porównanie złożoności algorytmów sortowania

Sprawdźmy złożoność obliczeniową poszczególnych algorytmów dla danego zbioru danych. W e‑materiale Jak wybrać odpowiedni algorytm sortowania?PK5Uba1BVJak wybrać odpowiedni algorytm sortowania? omawiamy to, w jaki algorytm sortowania należy wybrać w danym przypadku – nie będziemy brać tego teraz pod uwagę, natomiast warto mieć to w pamięci w kontekście tego, o czym już zostało powiedziane – na efektywność algorytmu wpływa nie tylko złożoność obliczeniowa, ale również to, czy jest odpowiednim wyborem dla danego problemu.

Załóżmy, że chcemy posortować niemalejąco dany zbiór: {2, 7, 0, 5, 2, 3, 15, 1, 9, 12, 94, 87}. Jak będzie wyglądać złożoność obliczeniowa poszczególnych algorytmów?

Aby określić liczbę operacji dla obu algorytmów, musimy wziąć pod uwagę ich złożoność obliczeniową.

Wiemy, że złożoność algorytmu sortowania przez wybieranie wynosi $O(n^2)$, zatem algorytm wykona maksymalnie 144 operacje. Natomiast liczba faktycznych operacji może być inna. W przypadku implementacji zaprezentowanej w e‑materiale dotyczącym sortowania przez wybieranie możemy określić, że dla podanych danych zostanie wykonanych 66 operacji porównania oraz 11 operacji zamiany. Daje to w sumie 77 operacji.

Złożoność algorytmu sortowania przez wstawianie do czynienia mamy ze złożonością $O(n^2)$, zatem algorytm również wykona maksymalnie 144 operacje. Natomiast w przypadku tego algorytmu liczba faktycznych operacji może być inna. W przypadku implementacji zaprezentowanej w e‑materiale dotyczącym sortowania przez wstawianie możemy określić, że dla podanych danych zostanie wykonanych 55 operacji porównania oraz 16 operacji zamiany. Daje to w sumie 71 operacji.

Algorytm sortowania bąbelkowego charakteryzuje się złożonością $O(n^2)$, zatem algorytm wykona maksymalnie 144 operacje. Natomiast liczba faktycznych operacji może być inna. W przypadku implementacji zaprezentowanej w e‑materiale dotyczącym sortowania bąbelkowego możemy określić, że dla podanych danych zostanie wykonanych 66 operacji porównania oraz 43 operacje zamiany. Daje to w sumie 109 operacji.

W przypadku sortowania kubełkowego do czynienia mamy ze złożonością $O(n + k)$ dla przypadków optymistycznego i średniego oraz $O(n^2)$ dla przypadku pesymistycznego. Wiemy, że $n$ oznacza liczbę elementów w zbiorze. Co jednak z $k$? Jest to liczba kubełków. Liczbę kubełków obliczamy, odejmując od największej wartości w tablicy wartość najmniejszą oraz dodając do tego $1$.

W analizowanym przypadku $k = 94 - 0 + 1$. Algorytm wykonałby maksymalnie 144 operacje (dla przypadku pesymistycznego) oraz 107 dla przypadków optymistycznego oraz średniego.

Natomiast liczba faktycznych operacji może być inna. W przypadku implementacji zaprezentowanej w e‑materiale dotyczącym sortowania kubełkowego możemy określić, że dla podanych danych zostanie wykonanych 12 operacji zliczeń oraz 95 operacji inicjalizacji kubełków. Daje to w sumie 107 operacji.

W analizowanym przypadku najlepszym wyborem byłby zatem algorytm sortowania przez wybieranie.

Dlaczego do określania złożoności czasowej używamy notacji „duże O”? Dokładne wyznaczenie czasu realizacji algorytmu jest bardzo trudne. Istnieje wiele czynników, które trzeba by było wziąć pod uwagę, m.in. szybkość wykorzystywanego procesora oraz pamięci czy język programowania. Dlatego zamiast podawania dokładnej liczby sekund wyznaczamy pewien rząd wielkości, który ułatwia przybliżenie czasu wykonywania programu i jest niezależny od środowiska.

Słownik