algorytm

Algorytmy – wprowadzenie

Długość wpisu: 1-3 minuty

Czego się dowiesz:

  • czym jest notacja duże 0
  • jak mierzyć czas algorytmów

W potocznym, uproszczonym języku „algorytm” to zestaw instrukcji, które opisują jak po kolei, krok po kroku, wykonać pewne zadanie, doprowadzić do pewnego wyniku. Algorytmy możemy sklasyfikować m.in. po dwóch kryteriach: szybkości działania oraz rodzaju rozwiązywanych problemów.

Dla każdego programisty potrzebna, wręcz niezbędna, jest podstawowa wiedza o algorytmach. A tej, oprócz na studiach, ciężko się nauczyć na przykład na bootcampach programistycznych. Nie znam przyczyny tego stanu rzeczy (może są ważniejsze sprawy), jednak aktualnie algorytmy wróciły do łask. Warto więc zaznajomić się z podstawami, wiedzieć jakie są słabe i mocne strony poszczególnych z nich. Przydatnym jest też umieć porównać dwa algorytmy ze sobą na przykład pod względem szybkości działania.

Czym jest szybkość działania algorytmu i jak ją zmierzyć ?

Zacznę od standardowego przykładu związanego z wyszukiwaniem. Załóżmy, że chcesz zgadnąć jaką liczbę pomyślałem z przedziału od 1 do 100. Zadając po kolei pytania o liczby – w najgorszym przypadku będzie trzeba zadać 100 pytań. Jest to przykład wyszukania prostego. Za każdym razem eliminowana jest jedna liczba.

Istnieje szybszy sposób znajdowania tej liczby. Załóżmy więc, że mamy posortowany zbiór liczb z tego samego przedziału od 1 do 100. Teraz wystarczy za każdym razem podzielić zbiór liczb na połowę, czyli w tym przypadku 50 i zapytać, czy szukana liczba jest mniejsza, czy większa, a może równa. W ten sposób za każdym razem eliminuje się połowę zbioru. Dzięki temu ilość prób skracana jest do maksymalnie 7.

Wyszukiwanie binarne, bo tak nazywa się ten algorytm jest bardzo efektywne, gdyż w tym przypadku wystarczy jedynie 7 prób.

Dla zmierzenia szybkości działania algorytmów nie używa się sekund ani w ogóle miary czasowej. Czas wykonywania algorytmu wyraża się w notacji dużego O. W powyższym przykładzie zapis w notacji dużego O dla wyszukiwania prostego wyglądałby następująco:

O(n)

Ten zapis oznacza, że mając n = 100 trzeba wykonać 100 operacji porównania lub zgadywania liczby j/w.

Dla wyszukania binarnego, gdzie za każdym razem zostaje połowa zbioru, zapis wygląda inaczej:

O(log n)

Logarytm jest przy podstawie z 2. Dla przypomnienia logarytmów dodam, że oznacza to do jakiej potęgi należy podnieć liczbę 2, aby otrzymać n. Przykład: ile operacji należy wykonać przy zbiorze złożonym z 8 elementów ??. Skoro 2 podniesione do potęgi 3 daje osiem, więc odpowiedź to: 3 operacje sprawdzenia należy wykonać dla zbioru składającego się z 8 liczba, wykorzystując algorytm wyszukiwania binarnego.

Dzięki takiej notacji można porównywać ze sobą algorytmy, sprawdzać jak będą się zachowywały w miarę wzrostu liczebności zbioru liczb. I dzięki temu dokonać trafniejszego wyboru między na przykład implementacją bardziej złożonego algorytmu, ale szybszego, czy wolniejszego algorytmu, ale działającego wystarczająco dobrze na danym zbiorze liczb.