Programisto, nie zapominaj o algorytmach! #2

W poprzednim odcinku rozpoczęliśmy temat algorytmiki i powiedzieliśmy co nieco o złożoności obliczeniowej. Pewnie część z Was głowi się – jak to właściwie obliczyć? Spróbujemy sobie dzisiaj odpowiedzieć na to pytanie i (z pewną dokładnością) przeanalizować złożoność obliczeniową kawałków kodu. Temat wymagający pełnego skupienia 🙂

Analiza złożoności obliczeniowej

Przypomnijmy, że będziemy analizować algorytmy w notacji wielkiego O – czyli takiej, która pomija elementy nieistotne przy wzroście danych. Więcej informacji o tej notacji znajdziecie w naszym poprzednim tekście „Programisto, nie zapominaj o algorytmach! #1”.

Każdą analizę zaczynamy od ustalenia operacji dominujących – czyli takich, które najczęściej będą wykonywane. Następnie zastanawiamy się ile razy ta operacja zostanie wykonana.

W następującym pseudokodzie:

a = 0
for(i=0;i<n;i++) {
  a = a + 1
}

operacją dominującą będzie dodawanie a = a + i – będziemy musieli zatem oszacować ile razy ta operacja zostanie wykonana. Jest ona wewnątrz pętli for, która zostanie wykonana n razy. Zatem dla dostatecznie dużego n, czas wykonania naszego kodu będzie równy czasowi n operacji dodawania. Przyjąć możemy, że dodawanie jedynki będzie odbywać się w czasie stałym (zatem bez wpływu w notacji O). Czyli złożoność rośnie liniowo zależnie od parametru wejściowego n. Stąd, ten (dosyć prosty algorytm) będzie złożoności O(n) (bo czynność dominująca o stałym czasie zostanie wykonana n razy).

Podwójna pętla

Zastanówmy się nad prostym przypadkiem podwójnej pętli:

a = 0
for(i=0;i<n;i++) {
  for(j=0;j<n;j++) {
    a = a + 1
  }
}

Znowu, operacją dominującą będzie dodawanie. Czeka nas więc szacowanie pętli (dwóch!). Pętla wewnętrzna wykona się n razy (czyli nasze dodawanie też) dla każdego przebiegu pętli zewnętrznej. Skoro ona też wykona się n razy, to operacja dominująca wykona się n·n = n² Stąd złożoność wyniesie O(n²) (bo czynność dominująca o stałym czasie zostanie wykonana n·n razy).

Sortowanie bąbelkowe

Spójrzmy jeszcze na przypadek tzw. sortowania bąbelkowego – czyli jednego z prostszych algorytmów sortowania:

func bubblesort(a) {
  for(i=1;i<len(a);i++) {
    for(j=0;j<len(a)-1;j++) { if a[j] > a[j + 1] {
        swap(a[j], a[j + 1])
      }
    }
  }
}

Spróbujcie sami oszacować jaka jest złożoność tego algorytmu (przyjmijcie, że swap działa w stałym czasie).

Uważaj na pułapki

Musimy jednak uważać na pewną pułapkę! Przypuśćmy, że mamy następujący kod napisany w języku Java:

 public static TreeSet<Integer> addElements(int n) {
    TreeSet<Integer> treeSet = new TreeSet<Integer>();
    for(int j=0;j<n;j++) {
        treeSet.add(j);
    }
    return treeSet;
}

 

Program ten dodaje do pewnej struktury danych, kolejne liczby naturalne, aż do n.
Operacją dominującą tutaj będzie instrukcja treeSet.add(j), więc kusić może stwierdzenie, że algorytm ten działa w czasie liniowym O(n) (jak poprzednio). Jednakże spojrzenie do dokumentacji, sprowadza nas nieco na ziemię:

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

W związku z tym musimy wziąć poprawkę – nasza operacja dominująca ma złożoność O(log n), a sama zostanie wykonana n razy. Zatem złożoność algorytmu finalnie to O(n log n).

Podane do tej pory algorytmy miały jedną wspólną cechę – zachowywały się tak samo dobrze (lub źle) –  niezależnie od układu danych wejściowych. Zwykle w algorytmice rozważamy najczęściej jednak dwa rodzaje danych – pesymistyczne (czyli najbardziej złośliwe) i losowe (czyli typowe). Możemy też rozważyć optymistyczne, aczkolwiek jest to jednak dosyć rzadko spotykany przypadek.

Przyjrzyjmy się takim danym na bazie szukania pewnego elementu w nieposortowanej tablicy. W takim wypadku jedyną opcją będzie sprawdzenie wszystkich elementów od początku do końca.

Optymistycznie trafimy za pierwszym razem. Zatem optymistyczna złożoność obliczeniowa wyniesie O(1). Prawdopodobieństwo takiego zdarzenia jest jednak pomijalne.
Pesymistycznie – szukane dane będą na samym końcu. Zatem O(n).
Średnio możemy przyjąć, że szukany element będzie w połowie – zatem O(½ n) (co jak zauważycie poniżej, wynosi dokładnie tyle samo co O(n)).

Własności notacji O

Tak naprawdę złożoność obliczeniową możemy opisać przy pomocy dowolnej funkcji – jednakże z uwagi na pewne własności notacji O możemy pominąć:

  • dodawanie stałych (O(n+1), to to samo co O(n)),
  • mnożenie przez stałą (O(2n), to to samo co O(n))
  • dodawanie czynników tzw. niższych rzędów (przez niższych rzędów rozumiemy rosnące wolniej) (O(2n2+n), to to samo co O(n2)).

Należy jednak uważać – np. czy O(log (n) +n0.00000000000001)zapiszemy jako O(log (n) ) czy jako O(n0.00000000000001)? Tutaj niestety wymagana jest od nas dodatkowa wiedza – logarytm co do zasady rośnie wolniej niż dowolny wielomian. Najczęściej wymieniane funkcje służące do opisu złożoności to (wymienimy je w hierarchii szybkości rośnięcia):

O(1), O(log (n) ), O(n), O(nlog (n) ), O(n²), O(n³), O(nA), O(2n), O(n!)

(gdzie A – dowolna dodatnia liczba całkowita > 3).

Złożoność dużej liczby algorytmów możecie znaleźć na stronie Bigocheatsheet.

W następnych częściach przypatrzymy się niektórym spośród algorytmów i struktur danych oraz spróbujemy wytłumaczyć sobie dlaczego mają akurat taką, a nie inną złożoność.

Site Footer

Sliding Sidebar