Algorytm

Algorytm genetyczny, schemat blokowy (1) Przykład zapisu algorytmu za pomocą schematu blokowego

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

Zapis algorytmu

Algorytm można zapisać na różne sposoby. Najczęściej stosowane metody zapisu algorytmu to:

  • język naturalny (opis słowny),
  • schemat blokowy,
  • pseudokod (zapis przypominający język programowania, jednak nie będący nim),
  • język programowania.

Złożoność obliczeniowa

Do oceny algorytmu zazwyczaj wyznacza się jego złożoność czasową i pamięciową, czyli zależność pomiędzy rozmiarem danych wejściowych a czasem wykonania algorytmu i ilością wymaganej pamięci. Czas działania algorytmu jest wyrażony jako liczba operacji elementarnych (np. operacji porównania czy przypisania), które trzeba wykonać. Obliczanie czasu w fizycznych jednostkach byłoby znacznie mniej uniwersalne, ponieważ zależałoby to m.in. od szybkości komputera. Aby uprościć analizę, najczęściej bierze się pod uwagę wyłącznie wybrane operacje, określane jako operacje dominujące – są to operacje, których liczba wykonań jest proporcjonalna do liczby wykonań wszystkich operacji elementarnych.

Zazwyczaj nie jest potrzebna postać funkcji określającej złożoność, ale jedynie jej rząd wielkości. Jest to określane jako asymptotyczna złożoność obliczeniowa. Do oznaczania tej złożoności powszechnie stosuje się tzw. notację dużego O. Notacja ta określa asymptotyczne ograniczenie górne funkcji złożoności. Jeśli funkcja jest rzędu O(g(n)), to dla wystarczająco dużego n spełniona jest zależność 0≤f(n)≤cg(n), gdzie c jest stałą.

Powszechnie uznaje się, że akceptowalne są algorytmy o złożoności co najwyżej wielomianowej (O(nk), gdzie k nie zależy od rozmiaru danych wejściowych). Algorytmy o złożonościach wyższych rzędów (np. O(kn), O(n!), O(nn)) w praktyce działają w rozsądnym czasie tylko dla danych wejściowych o niewielkich rozmiarach.

Bibliografia

  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
  • Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010, ISBN 9788373356689.
Ocena: -2 Tak Nie
Liczba głosów: 14.

Dodano: 27 czerwca 2017 18:10, ostatnia edycja: 30 stycznia 2019 15:49.

REKLAMA

Zobacz też

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ Czytaj całość
Sortowanie bąbelkowe (ang. bubble sort) – prosty algorytm sortowania polegający na porównywaniu za sobą sąsiednich elementów. Złożoności czasowa algorytmu wynosi O(n2).
→ Czytaj całość

Metoda Otsu – algorytm służący do binaryzacji obrazu, czyli przekształcenia obrazu w odcieniach szarości do obrazu binarnego. Metoda ta realizuje progowanie globalne – dla całego obrazu wyznaczany jest jeden próg jasności, a następnie wszystkim pikselom jaśniejszym od tego progu przypisywana jest jedna wartość, a ciemniejszym druga.

Algorytm jest oparty na analizie histogramu. Przygotowanie histogramu polega na zliczeniu pikseli w każdym możliwym odcieniu (zazwyczaj liczba odcieni wynosi 256, gdyż tyle da się zakodować w jednym bajcie). Następnie należy sprawdzić każdy możliwy próg jasności i wybrać ten, dla którego wariancja międzyklasowa jest największa (lub suma ważona wariancji wewnątrzklasowych jest najmniejsza).

Jeśli obrazem wejściowym jest obraz kolorowy, można go łatwo sprowadzić do odcieni szarości. W przypadku kolorów zakodowanych w RGB najprostszym rozwiązaniem jest uśrednienie dla każdego piksela wartości wszystkich trzech kanałów.

→ Czytaj całość
Polityka prywatnościKontakt