Algorytm: co to jest, cechy i sposoby zapisu z przykładami

Co to jest algorytm

Algorytm jest przepisem postępowania. Mówi, od czego zacząć, co zrobić w kolejnych krokach i kiedy skończyć. Nie jest jednak ograniczony do komputerów: sposób dodawania pisemnego też jest algorytmem, bo każdy, kto go zna, wykona go tak samo.

W informatyce algorytm to dobrze określona procedura obliczeniowa. Przyjmuje dane wejściowe (na przykład listę liczb) i produkuje dane wyjściowe (na przykład największą z nich). Program komputerowy jest zapisem algorytmu w języku, który rozumie maszyna.

Słowo „algorytm” pochodzi od zlatynizowanej wersji nazwiska al-Chuwarizmiego, matematyka działającego w IX wieku.

Przykład z codzienności: przepis na herbatę

1. Nalej do czajnika wodę.
2. Włącz czajnik i poczekaj, aż woda się zagotuje.
3. Włóż torebkę do kubka i zalej ją wodą.
4. Odczekaj kilka minut.
5. Wyjmij torebkę.

Dane wejściowe to woda, kubek i torebka, wynik to gotowa herbata. Każdy krok jest wykonalny, kolejność jest ustalona, a całość kończy się po pięciu krokach. W przepisie kuchennym zwykle brakuje precyzji (jak długo „kilka minut”), dlatego algorytm informatyczny wymaga dokładniejszych poleceń.

Cechy algorytmu

Poza tym zwraca się uwagę na efektywność: ile kroków (czasu) i pamięci potrzeba przy dużych danych. Ten sam problem często rozwiązuje się kilkoma algorytmami o różnej szybkości.

Sposoby zapisu algorytmu

Algorytmy opisuje się w języku naturalnym, w postaci schematów blokowych oraz w pseudokodzie. Czwartą formą jest program w wybranym języku.

Schemat blokowy ma własne zasady rysowania i wymaga osobnego omówienia. Poniższe przykłady zapisano w pozostałych trzech formach.

Przykład 1: największa liczba na liście

Lista kroków.

1. Przyjmij pierwszą liczbę z listy za największą dotychczas.
2. Przejrzyj kolejno pozostałe liczby.
3. Jeśli liczba jest większa od największej dotychczas, zapamiętaj ją jako nową największą.
4. Po przejrzeniu całej listy wynikiem jest zapamiętana liczba.

Pseudokod.

dane: lista L (niepusta)
m := L[1]
dla każdego x w L od drugiego elementu:
    jeśli x > m:
        m := x
wynik: m

Python.

def maks(lista):
    m = lista[0]
    for x in lista[1:]:
        if x > m:
            m = x
    return m

print(maks([7, 3, 12, 9, 5]))  # 12

Algorytm przegląda każdy element raz, więc dla listy n liczb wykonuje około n porównań. Zakłada niepustą listę. To warunek na dane wejściowe, bez którego algorytm nie byłby poprawny.

Przykład 2: największy wspólny dzielnik (algorytm Euklidesa)

Największy wspólny dzielnik (NWD) dwóch liczb to największa liczba, przez którą dzielą się obie. Algorytm Euklidesa wyznaczania NWD opisano już w starożytnej Grecji. Opiera się na tym, że NWD(a, b) = NWD(b, a mod b), gdzie „a mod b” to reszta z dzielenia a przez b.

Lista kroków.

1. Weź dwie liczby naturalne a i b.
2. Jeśli b = 0, wynikiem jest a.
3. W przeciwnym razie oblicz resztę r z dzielenia a przez b, podstaw a := b oraz b := r i wróć do kroku 2.

Pseudokod.

dane: liczby naturalne a, b
dopóki b ≠ 0:
    r := a mod b
    a := b
    b := r
wynik: a

Python.

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(nwd(252, 105))  # 21

Przebieg dla a = 252 i b = 105:

Algorytm kończy się, bo reszta z dzielenia jest zawsze mniejsza od dzielnika, więc liczby maleją i po skończonej liczbie kroków pojawia się reszta 0. To uzasadnienie cechy skończoności.

Przykład 3: wyszukiwanie w liście

Wyszukiwanie liniowe sprawdza elementy po kolei, aż znajdzie szukany albo dojdzie do końca.

def szukaj(lista, cel):
    for i, x in enumerate(lista):
        if x == cel:
            return i
    return -1

print(szukaj([7, 3, 12, 9, 5], 12))  # 2 (numeracja od 0)
print(szukaj([7, 3, 12, 9, 5], 4))   # -1: nie ma takiej liczby

Jeśli lista jest uporządkowana rosnąco, można skorzystać z wyszukiwania binarnego: porównaj szukaną wartość ze środkowym elementem i odrzuć połowę listy, w której na pewno jej nie ma.

def szukaj_binarnie(lista, cel):
    lo, hi = 0, len(lista) - 1
    while lo <= hi:
        s = (lo + hi) // 2
        if lista[s] == cel:
            return s
        if lista[s] < cel:
            lo = s + 1
        else:
            hi = s - 1
    return -1

L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(szukaj_binarnie(L, 23))  # 5

Dla tej listy i liczby 23 wystarczą trzy porównania (sprawdzane elementy: 16, 56, 23), a wyszukiwanie liniowe sprawdziłoby sześć elementów. Różnica rośnie z długością listy: przy tysiącu elementów wyszukiwanie binarne wymaga najwyżej 10 porównań, a liniowe nawet 1000. Cena za szybkość to wymóg, by dane były posortowane.

Jak sprawdzić, czy algorytm jest poprawny

1. Wypisz dane wejściowe, które algorytm ma obsłużyć, i wynik, jakiego oczekujesz.
2. Przejdź ręcznie krok po kroku przez mały przykład, najlepiej w tabeli zmiennych, jak dla NWD wyżej.
3. Sprawdź przypadki skrajne: pusta lista, jeden element, liczby równe, zero.
4. Upewnij się, że każda pętla się kończy: coś musi zmieniać się w stronę warunku zatrzymania.

Zobacz też: Rekurencja, Rok przestępny, Sortowanie bąbelkowe.

Najczęstsze pytania (FAQ)

Czy algorytm musi być zapisany w języku programowania?

Nie. Język programowania to jedna z form zapisu. Algorytm można opisać słowami, schematem blokowym albo pseudokodem. Kod jest potrzebny dopiero wtedy, gdy ma go wykonać komputer.

Czym różni się algorytm od programu?

Algorytm to ogólna metoda rozwiązania zadania, niezależna od języka. Program to zapis tej metody w konkretnym języku programowania, który można uruchomić na komputerze. Ten sam algorytm da się zapisać w wielu językach.

Czy ten sam problem można rozwiązać różnymi algorytmami?

Tak. Wyszukiwanie w liście można wykonać liniowo albo binarnie, a liczby można sortować wieloma metodami. Algorytmy różnią się liczbą kroków i zużyciem pamięci, dlatego wybiera się je zależnie od rozmiaru i postaci danych.

Czy algorytm może się nie zatrzymać?

Wtedy nie spełnia definicji algorytmu, bo ta zakłada skończoność. W praktyce błąd w warunku pętli powoduje, że program działa w nieskończoność.

Od czego zacząć naukę pisania algorytmów?

Od rozpisania zadania w liście kroków i sprawdzenia go na małym przykładzie. Dopiero potem przełóż go na pseudokod i kod. Dobre ćwiczenia to znalezienie największej liczby, obliczanie NWD i wyszukiwanie w liście.