Dziś artykuł numer 7, czyli złożoność obliczeniowa, czyli temat ogromny, rozległy i traktowany jako osobny dział informatyki. Uwielbiam takie wyzwania, sam na temat złożoności wiele razy czytałem, tworzyłem publikacje w ramach zajęć na studiach i postanowiłem, że poświęcę mu miejsce na blogu. Przypuszczam, że nie wyczerpię tematu w 100%, dlatego liczę na Twój komentarz poniżej, gdyby czegoś zabrakło. 

Pochylę się nad zagadnieniami takimi jak:

  • Czym jest złożoność obliczeniowa?
  • Do czego używana jest notacja „duże O”?
  • Co oznacza Omega i Theta?
  • Na jakie kategorie dzielimy złożoność obliczeniową?
  • Kto jest twórcą?

Mam nadzieję, że po przeczytaniu tego artykułu będziesz wiedział/a więcej na temat złożoności obliczeniowej w algorytmice. Jeżeli natomiast temat nie jest Ci obcy, to pomoże Ci w uporządkowaniu wiedzy. Jest to temat ciekawy i pod wieloma aspektami ważny, którego żaden programista nie powinien go bagatelizować.

Wszystko, czego się dotąd nauczyłeś, zatraci sens, jeśli nie potrafisz znaleźć zastosowania dla tej wiedzy.

Paulo Coelho

Na koniec wstępu dodam, że osobiście nigdy nie spotkałem się z tym tematem podczas rozmów o pracę czy dyskusji wewnątrz zespołów developerów. Ale zaufaj mi, ponieważ temat ten pomaga w wielu kwestiach, bo już sama świadomość tego, co wpływa na szybkość działania kodu, jest niezwykle ważna.

Zaczynamy!

Złożoność obliczeniowa — Wprowadzenie

Bardzo ciężko oszacować potrzebne zasoby do wykonania określonego algorytmu, ponieważ w dzisiejszych czasach dostępne są przeróżne urządzenia, od telefonów i tabletów, po laptopy i komputery a kończąc na supermaszynach typu serwery. Z pomocą przychodzi teoria złożoności obliczeniowej zaproponowana przez amerykańskich informatyków Jurisa Hartmanisa i Richarda Stearnsa (otrzymali zresztą za to nagrodę Turinga w 1993 roku, która jest traktowana jako informatyczny odpowiednik nagrody Nobla).

Złożoność obliczeniowa jest częścią działu informatyki teoretycznej o nazwie teorii obliczeń. Same zagadnienia związane z teorią obliczeń wywodzą się z matematyki, dlatego w dzisiejszym wpisie będzie trochę o niej. Głównym celem tego działu jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Jako zasób możemy rozumieć złożoność czasową lub pamięciową.


Złożonością czasową wyrażamy jednostkę czasu lub operacji dominujących, jaką potrzebuje algorytm, by zakończyć swoje działanie. Nie skłamię, jeżeli napiszę, że 90% przypadków sygnowana jest operacjami dominującymi, a nie upływem czasu. Dzieje się tak dlatego, że wyniki są różne w zależności od rodzaju sprzętu, na jakim takie obliczenia będą wykonywane. Dlatego najczęściej złożoność czasowa podajemy w ilości operacji dominujących. Operacją dominującą w przypadku algorytmu nazwiemy część funkcji, która decyduje o długości działania. Jest to na przykład operacja dodawania i mnożenia w przypadku algorytmu mnożenia macierzy, przeszukiwanie zbiorów natomiast będzie bazowało na operacji porównania, a w sortowaniu bąbelkowym będzie to podwójna pętla.

Przypadek złożoności pamięciowej jest dużo prostszy i niezależny od sprzętu. Tu po prostu patrzymy na to, ile zasobu w postaci komórek pamięci algorytm będzie wymagał. 

Rodzaje złożoności

Każde zużycie zasobu przez algorytm, niezależnie czy chodzi o złożoność pamięciową, czy czasową, można przedstawić w trzech odmianach:

  • Pesymistyczną
  • Optymistyczną
  • Średnią

Możemy zobrazować to w następujący sposób. Mamy tablicę składającą się z n elementów z zakresu od 1 do 100000. Działanie algorytmu niech będzie trywialnie proste, ponieważ mamy znaleźć liczbę 1992. Niech pętla for iteruje po wszystkich elementach w tablicy i sprawdza, co się może wydarzyć:

  • Najbardziej pesymistyczny przypadek, gdy liczba 1992 znajdzie się na ostatnim miejscu tablicy. Wtedy pętla będzie iterować aż do ostatniego elementu i złożoność w takim przykładzie wyniesie n.
  • Najbardziej optymistyczny przypadek, gdy liczba 1992 znajdzie się na pierwszym miejscu tablicy. Wtedy po jednej iteracji program zakończy działanie i złożoność będzie wynosić 1.
  • Przypadek spotykany najczęściej,  raz znajdziemy liczbę 1992 bliżej początku raz bliżej końca, ale uśredniając, będzie to blisko połowy zbioru. Wtedy złożoność średnia będzie równa n/2.

Złożoność obliczeniową możemy rozróżnić za pomocą następujących klasyfikatorów

stała [Θ(1)] – czas wykonania algorytmu jest stały i niezależny od rozmiaru danych wejściowych. Przykładem może być porównanie dwóch liczb w instrukcji warunkowej lub przypisanie wartości do zmiennej.

liniowa [Θ(n)] – czas działania jest proporcjonalny do rozmiaru danych wejściowych. Przykładem może być sortowanie przez zliczanie lub pozycyjne.

liniowo-logarytmiczna [Θ(n log n)] – złożoność jest iloczynem funkcji liniowej i logarytmicznej. Przykładem może być algorytm wyszukiwania interpolacyjnego.

logarytmiczna [Θ(log n)] – kiedy czas ten rośnie logarytmiczne wraz ze wzrostem wielkości danych. Logarytm o podstawie 2. Przykładem może być wyszukiwanie w drzewie BST (binarne drzewo poszukiwań).

kwadratowa [Θ(n2)] – liczba instrukcji algorytmu rośnie proporcjonalnie do kwadratu rozmiaru danych wejściowych. Przykładem może być sortowanie bąbelkowe lub przez wstawianie.

sześcienna [Θ(n3)] – liczba instrukcji algorytmu rośnie proporcjonalnie do sześcianu rozmiaru danych wejściowych. Przykładem może być mnożenie macierzy.

wielomianowa [Θ(nx + nx-1 + … + n1) ] – liczba instrukcji algorytmu rośnie proporcjonalnie do pewnego wielomianu rozmiaru danych wejściowych.

wykładnicza [Θ(2n)] – czas wykonania rośnie wykładniczo względem rozmiaru danych. Przykładem może być ciąg Fibonacciego.

silni [Θ(n!)] – czas wykonania rośnie z szybkością silni względem rozmiaru danych. Przykładem mogą być niektóre algorytmy operujące na grafach.

Notacja „duże O”

Powyżej przedstawiłem trzy rodzaje złożoności, gdzie najczęściej używaną jest złożoność O (asymptotyczne ograniczenie górne), nazywana jako „duże O” lub po prostu O. Notacja O przedstawia asymptotyczne tempo wzrostu, czyli określa zachowanie funkcji przy wzroście argumentów. Koncepcja dużego O została zaproponowana w 1894 roku przez niemieckiego matematyka Paula Bachmanna.

Ideą notacji dużego O nie jest dokładne oszacowanie złożoności obliczeniowej. Poniżej zaprezentowany jest wielomian trzeciego stopnia. Złożoność podanej funkcji możemy zapisać jako O(n3), ponieważ największy wpływ na funkcję będzie miało działanie 8n3 .

8n3 + 4n2 + 5n + 3 = 0

Jako przykład typowo programistyczny zobaczmy złożoność obliczeniową mnożenia macierzy A przez macierz B. Jak pamiętamy z matematyki (a jeżeli nie to zaprezentuję poniżej pomnożone macierze) mnożenie macierzy odbywa się poprzez przemnożenie elementów macierzy A przez elementy macierzy B i zsumowanie wartości mnożenia.

Złożoność obliczeniowa - przykład macierzy

1.1)    (2 * 6) + (2 * 2) + (7 * 1) + (4 * 5) = 43.00

1.2)    (2 * 9) + (2 * 3) + (7*1) + (4 * 4) = 47.00

2.1)    (5 * 6) + (9 * 2) + (3 * 1) + (8 * 5) = 91.00

2.2)    (5 * 9) + (9 * 3) + (3 * 1) + (8 * 4) = 107.00

3.1)    (7 * 6) + (8 * 2) + (7 * 1) + (4 * 5) = 85.00

3.2)    (7 * 9) + (8 * 3) + (7 * 1) + (4 * 4) = 110.00

Pseudokod do mnożenia macierzy wygląda mniej więcej tak jak poniżej. Jak widzimy, musimy wykonać aż trzy pętle, jedna zagnieżdżona w drugiej, więc iterujemy pionowo i poziomo, a w ostateczności znów w pionie, po macierzy wynikowej. Znacząca dla naszej funkcji jest zmienna n i jej wzrost spowoduje złożoność obliczeniową tego algorytmu. Sprawia to, że notacja dużego O wynosi O(n3).

for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        c[i][j] = 0;
        for (k = 0; k < n; k++)
        {
            c[i][j] = c[i][j] + a[i][k] * b[k][j];
        }
    }
}

Notacje pokrewne

Notacja duże O jest najczęściej używana i wszystkie pozostałe notacje nazywane są pokrewnymi. Dwie z nich, o których wspomniałem wyżej to duże Omega oraz duże Theta

Poniżej zaprezentowałem trzy wykresy dla każdej z trzech omawianych notacji. Przypadek dużego O przedstawia wykres g(n), który z góry ogranicza funkcję f(n). Zapis  f(n) = O(g(n)) oznacza to, że istnieje pewne miejsce na wykresie, nazywane w naszym przypadku n0, od którego funkcja f będzie mniejsza od funkcji g (będzie poniżej wykresu funkcji g). Dokładnie odwrotnie dzieje się w przypadku Ω. Od pewnego miejsca n0 funkcja f będzie większa od funkcji g.

Bardzo dobrze pokazuje notację Θ wykres numer trzy. Od pewnego miejsca n0 funkcja f będzie mieścić się pomiędzy funkcjami c1 * g(n) oraz c2 * g(n).

Złożoność obliczeniowa - wszystkie notacje

Czy wiesz, że…

Jednym z ciekawszych problemów przedstawianych w kontekście ogromnej złożoności algorytmu jest problem komiwojażera. Problem dotyka teoretycznie prostego zagadnienia, a mianowicie obliczenia najkrótszej drogi pomiędzy pewną liczbą miast. O ile problem jest rozwiązywalny dla małej liczby punktów na mapie, o tyle dla dużych liczb na ten moment nie jest możliwe wyliczenie najkrótszej możliwej trasy. Już dla 20 miast liczba możliwości równa jest 1016!

Z problemem już w XIX wieku zmagali się matematycy z całego świata. Do dziś walczą z nim, chociażby wielkie korporacje zajmujące się logistyką. Polecam zapoznać się z materiałem poniżej.

Złożoność obliczeniowa podsumowanie

Jak widzisz złożoność obliczeniowa to ciężki aspekt informatyki, jednak temat dotyczy teorii informatyki i bez dwóch zdań swoje początki miał w matematyce. Zagadnienie przedstawione w tym artykule to tylko wierzchołek góry lodowej i spokojnie mógłbym tu pisać z niespotykaną nigdzie dokładnością, stosując dziesiątki wzorów. Nie chciałem tego i postarałem się o jak najbardziej przystępne przekazanie podstawowych informacji.

Kolejny temat będzie dotyczył nauki programowani i mojej historii z tym związanej!

Zachęcam Cię do skonfrontowania tego materiału z innymi na ten temat dostępnymi w sieci lub publikacjach naukowych. Między innymi książki poniżej są dobrym rozszerzeniem tematu!

PS. Będę wdzięczny za komentarze pod tym postem!

PS2. Czeka też na Ciebie prezent. Wystarczy, że zapiszesz się na Newsletter poniżej!

PS3. Dołącz do naszej grupy na Facebook!


Subskrybuj

Zapisz się na Newsletter, odbierz NAGRODĘ w postaci e-booka z 10 omówionymi algorytmami pojawiającymi się w pytaniach podczas REKRUTACJI..

Dodatkowo otrzymuj co niedzielę informacje na temat nowych wpisów, wiadomości ze świata IT i matematyki oraz ciekawych wydarzeniach. Nie przegap i dołącz już dziś do 914 osób!.

Źródła

https://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa
http://home.agh.edu.pl/~horzyk/lectures/pi/ahdydpiwykl8.html
https://eduinf.waw.pl/inf/utils/010_2010/0216.php
http://xion.org.pl/files/texts/mgt/pdf/M_B.pdf
https://pl.wikibooks.org/wiki/Struktury_danych/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa
http://cpp0x.pl/kursy/Teoria-w-Informatyce/Zlozonosc-obliczeniowa/Rzedy-zlozonosci-obliczeniowej/427
http://www.algorytm.org/kurs-algorytmiki/zlozonosc-obliczeniowa.html
http://www.deltami.edu.pl/temat/informatyka/algorytmy/2019/03/28/Zlozonosc_obliczeniowa/
https://ksiegarnia.pwn.pl/Wprowadzenie-do-algorytmow,68706413,p.html
Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

6 komentarzy

  1. Zgadzam się że złożoność obliczeniowa to bardzo szeroki temat. Czytałem trochę o tym zagadnieniu w książce Davida Harel-a „Rzecz O Istocie Informatyki – Algorytmika”. Polecam tą książkę.

    Chyba w filmie The Code na Netflix, Marcus du Sautoy próbował rozwiązać problem komiwojażera obserwując i badając pszczoły latające po nektar. Ustawił on nektar w paru punktach kontrolnych (miasta) i obserwował poszczególne pszczoły jakimi trasami latają. Jak wiadomo pszczoły optymalizują swoje trasy intuicyjnie co jest wynikiem wielu milionów lat ewolucji. Nie jestem do końca pewny czy to w tym dokumencie był ten eksperyment.

    Czy myślisz Mateusz że komputery kwantowe rozwiążą ostatecznie problem komiwojażera?

    Pozdrawiam :-).

    • Cześć Mateusz, dziękuję Ci za komentarz i polecone materiały!

      Co do komputerów kwantowych to temat nie jest taki oczywisty. Co prawda wiele się od nich oczekuje ale myślę, że to na przestrzeni 50-100 lat zaczniemy z nich na serio korzystać.
      Byłem też na ciekawej międzynarodowej konferencji w zeszłym roku na temat właśnie kwantowej fizyki i komputeryzacji.

      Pozdrawiam, Mateusz.

  2. Notacja Θ nie dotyczy średniego czasu wykonania programu, tylko dokładnego, tj. daje jednocześnie ograniczenie górne i dolne różniące się o stały czynnik. W szczególności podany w ramach przykładu algorytm wyszukujący w tablicy liczbę 1992 nie ma złożoności Θ(n/2) – to by bowiem znaczyło, że dla pewnej stałej c > 0 algorytm nigdy nie działa szybciej niż c * n / 2, co jest nieprawdą, bo algorytm w szczęśliwym przypadku działa w czasie 1 niezależnie od n. Ponadto w tym przykładzie złożoność w ogóle nie daje się zapisać przy użyciu notacji Θ.

Napisz komentarz

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.