Programisto, nie zapominaj o algorytmach! #1

Każdy początkujący programista w swojej karierze trafia prędzej lub później na temat algorytmów i struktury danych. Czy to na studiach, czy na własną rękę, kiedy okazuje się, że cudowne rozwiązanie problemu jest skrajnie niewydajne. Odpowiedzi na pytanie: „Dlaczego mój program działa tak wolno?” udziela często algorytmika – nauka o algorytmach. Dzisiejszym wpisem zaczynamy cykl poświęcony właśnie tej grupie zagadnień.

Czym są algorytmy?

Algorytm według Słownika Języka Polskiego oznacza „ściśle określony ciąg czynności, których wykonanie prowadzi do rozwiązania jakiegoś zadania”. Dzisiaj przyjrzymy się działowi informatyki, który zajmuje się tworzeniem i analizą algorytmów.

Algorytmika jest nazywana czasem królową informatyki. Wydawać by się mogło, że w erze coraz szybszych komputerów, będziemy przykładać coraz mniejszą uwagę do szybkości działania algorytmów. Jednak tak się nie stało – zacznijmy od odpowiedzi na zasadnicze pytanie – dlaczego?

Problem komiwojażera

Rozważmy następujący problem – nazywany problemem komiwojażera. Mamy sprzedawcę, który jeździ od miasta, do miasta sprzedając swoje produkty. Chce odwiedzić wszystkie miasta na danym obszarze, podróż między każdą parą z nich chwilę trwa. Komiwojażer oczywiście ceni swój czas, zatem wyruszając z domu, chce odwiedzić wszystkie miasta, po czym znaleźć się jak najszybciej z powrotem domu. Jak wyznaczyć taką najkrótszą trasę?

Naiwnym podejściem byłoby sprawdzenie wszystkich możliwych kombinacji. Załóżmy, że mamy 100 miast. Jednakże jak zaczniemy to liczyć, okaże się, że liczymy i liczymy, i liczymy…

Podejście to stanowi tzw. rozwiązywanie problemu metodą brute-force (czyli brutalnej siły). Uporczywie przeszukujemy wszystkie możliwe kombinacje. Jak już wyliczymy wszystko – wtedy znamy najlepszą opcję. Taki algorytm musi wykonać około n! przeliczeń. Czyli dla 5 elementów – 120 operacji. Jest dobrze.

Jednak, gdy zaczniemy zwiększać liczbę miast, na przykład do 100, będziemy musieli wykonać jedyne… 9332621544394415268169923885626670049071596826438162146859296389521759
9993229915608941463976156518286253697920827223758251185210916864000000
000000000000000000 operacji. Niezbyt praktyczne i niezbyt możliwe do wyliczenia.

Jednak używając bardziej złożonych algorytmów, udało się wyznaczyć rozwiązanie problemu dla 85900 miast. Problem komiwojażera został uznany za jeden z najtrudniejszych problemów informatyki. Więc może jednak warto zainteresować się algorytmami?

Złożoność obliczeniowa

Spójrzmy teraz na problem z nieco bardziej formalnej strony – będzie nam to potrzebne żeby móc dobrze oszacować złożoność naszych algorytmów (co będziemy ćwiczyć w kolejnych artykułach), jak i zrozumieć dlaczego akurat jest ona tak istotna. Będzie nieco trudniej, ale liczę, że się nie zgubicie ;).

Nieformalnie nazywana wcześniej liczba przeliczeń, fachowo nazywa się złożonością obliczeniową. Mówimy, że jest to ilość́ zasobów niezbędna do wykonania algorytmu (zasoby to np. czas czy pamięć́). Inaczej można powiedzieć, że jest to pewnego rodzaju miara (czy metryka) do porównywania efektywności algorytmów. W ocenie efektywności najczęściej interesuje nas stosunek między rozmiarem danych N (np. liczbą miast w problemie komiwojażera), a czasem wykonania obliczeń T.
Stosunek ten może być wyrażony bardzo skomplikowana funkcją, stąd upraszczamy nieco sytuację rozważając tzw. złożoność asymptotyczną – czyli jak szybko funkcja rośnie przy zwiększaniu rozmiaru danych. Służy do tego notacja wielkie O, która pomija elementy które są nieistotne przy wzroście ilości danych.

Przykład

f(n)=n²+100n+1000

Załóżmy, że funkcja ta opisuje złożoność jakiegoś algorytmu – czyli ile operacji musi wykonać dany algorytm dla danych wejściowych wielkości n. Zakładając, że każda operacja zajmuje sekundę, ile sekund zajmie wykonywanie algorytmu?
Zobaczmy jak ta funkcja zachowuje się, gdy zwiększamy parametr n (co byłoby symulacją zwiększania ilości danych), a także ile wynoszą wartości poszczególnych składników sumy.

n f(n)=n²+100n+1000 100n 1000
1 1101 1 100 1000
10 2100 100 1000 1000
100 21000 10000 10000 1000
1000 1101000 1000000 100000 1000
10000 101001000 100000000 1000000 1000
100000 10010001000 10000000000 10000000 1000
1000000 1000100001000 1000000000000 100000000 1000

A ile w takim razie wynosi procentowy udział każdego składnika w finalnej sumie?

n n^2 100n 1000
1 0,09% 9,08% 90,83%
10 4,76% 47,62% 47,62%
100 47,62% 47,62% 4,76%
1000 90,83% 9,08% 0,09%
10000 99,01% 0,99% 0,00%
100000 99,90% 0,10% 0,00%
1000000 99,99% 0,01% 0,00%

Składnik 1000 który na początku tak bardzo przeważał, okazuje się nie mieć zupełnie żadnego znaczenia przy dużych liczbach! Tak naprawdę jeśli interesuje nas tylko szybkość wzrostu funkcji, możemy powiedzieć, że dla dużych liczb zachowuje się ona tak samo jak funkcja n².

algorytmy

A przekładając to na formalny język – funkcja f(n)=n²+100n+1000, jest tego samego rzędu f(n)=n². Symbolicznie f(n)∈Ο(n²).
Notację taką nazywamy notacją wielkiego O. Jest ona podstawową notacją przy analizie algorytmów. W jednym z kolejnych artykułów nauczycie się analizować proste (ale też i te bardziej złożone) algorytmy i wyznaczać samemu przybliżoną złożoność obliczeniową swojego kodu.

Warunek stopu

Innym pytaniem (aczkolwiek bardzo podobnym) jest pytanie – czy algorytm kiedyś zakończy działanie?
Pytanie wydawać by się mogło bardzo trywialne, weźmy na przykład następujący fragment pseudokodu:

for(i=0;i<10;i++) {
// do something
}

W tym wypadku odpowiedź jest oczywista – algorytm zatrzyma się. Po ilu iteracjach możecie policzyć na palcach sami.
Jednakże sam problem czy algorytm zakończy działanie, nazywamy problemem stopu jest kolejnym bardzo trudnym problemem informatycznym. Rozważmy nieco inny (niezbyt sensowny) kawałek kodu:

while(x != 1) {
  if(x % 2 == 0) {
    x = x + 2
  } else {
    x = x - 2
  }
}

Tym razem na pierwszy rzut oka nie widać – wymaga od nas głębszej analizy problemu. Przed czytaniem dalej – przepisz ten fragment kodu do swojego ulubionego języka programowania i zbadaj sam kiedy algorytm kończy działanie, a kiedy wpada w nieskończoną pętlę.
Zrobione? To wracamy.

Przeanalizujmy ten kod. Główna pętla wykonuje się tak długo, dopóki x jest różne od jedynki. Możliwe są dwa główne przypadki – gdy x > 0 lub x < 0. Zacznijmy od pierwszego.

Zauważmy, że operacje w ifach nie będą zmieniać parzystości! Zatem jeżeli x jest dodatnią liczbą parzystą – program nigdy się nie zatrzyma. Bo nie trafimy w wartość 1, która mogłaby skończyć działanie pętli while. Jeżeli zaś x jest dodatnią liczbą nieparzystą – program skończy działanie, bo odejmując 2 dostatecznie wiele razy od liczby nieparzystej, w końcu dojdziemy do 1. W przypadku liczby ujemnej – program nigdy się nie zatrzyma. Jeżeli dostaniemy ujemną liczbę parzystą – tak samo jak przy dodatniej. Jeżeli otrzymamy ujemną liczbę nieparzystą – będzie ona wciąż się zmniejszać i nie ma szans trafić w jedynkę.

Uff, już nie było tak łatwo, prawda? Ogólnie problem stopu możemy sformułować następująco:
czy dany program, przy określonych danych wejściowych zatrzyma się (zakończy działanie w skończonym czasie)?
O programie, który ma taką własność mówimy, że ma własność stopu. Nie istnieje uniwersalny sposób rozstrzygnięcia tego problemu. Jedyną możliwością jest analiza kodu. Najlepiej jednak pisać kod w którym dbamy o to, żeby dało się to jednoznacznie stwierdzić.

Poprawność algorytmu

Jeżeli algorytm spełnia warunek stopu, a także daje poprawne odpowiedzi możemy powiedzieć, że jest on poprawny (formalnie można również dowodzić poprawności algorytmów). Wtedy ma sens analiza jego złożoności obliczeniowej, czego uczyć się będziemy już następnym razem…

 

Źródła:

Wstęp do programowania/wstęp do algorytmów

„Wprowadzenie do algorytmów ” Cormen Thomas H., Leiserson Charles E., Rivest Ronald L, Clifford Stein

„Algorytmy” Almanach George Heineman, Gary Pollice, Stanley Selkow

Site Footer

Sliding Sidebar

Dowiedz się więcej

Zostaw nam swój e-mail i daj znać, które miasto Cię interesuje.
Prześlemy Ci informator, w którym znajdziesz szczegóły naszych kursów, tego jak uczymy i jak zapisać się na kurs.

Administratorem danych osobowych jest Akademia IT Sp. z o.o. Dane zbierane są w celu wysyłki informacji marketingowych. Osoba, której dane dotyczą ma prawo dostępu do treści swoich danych oraz ich poprawiania. Podanie danych jest dobrowolne. Wyrażam zgodę na przetwarzanie przez Akademia IT Sp. z o.o. moich danych osobowych dla celów marketingowych. Oświadczam, że zostałem poinformowany/zostałam poinformowana o tym, iż administratorem danych osobowych jest Akademia IT Sp. z o.o. z siedzibąw Warszawie, a także o dobrowolności podania danych i przysługujących mi prawach, w szczególności o prawie dostępu do treści danych i ich poprawiania.

Dowiedz się więcej

Zostaw nam swój e-mail i daj znać, które miasto Cię interesuje.
Prześlemy Ci informator, w którym znajdziesz szczegóły naszych kursów, tego jak uczymy i jak zapisać się na kurs.

Administratorem danych osobowych jest Akademia IT Sp. z o.o. Dane zbierane są w celu wysyłki informacji marketingowych. Osoba, której dane dotyczą ma prawo dostępu do treści swoich danych oraz ich poprawiania. Podanie danych jest dobrowolne. Wyrażam zgodę na przetwarzanie przez Akademia IT Sp. z o.o. moich danych osobowych dla celów marketingowych. Oświadczam, że zostałem poinformowany/zostałam poinformowana o tym, iż administratorem danych osobowych jest Akademia IT Sp. z o.o. z siedzibąw Warszawie, a także o dobrowolności podania danych i przysługujących mi prawach, w szczególności o prawie dostępu do treści danych i ich poprawiania.