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: 12.

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

REKLAMA

Zobacz też

Kolejka (ang. Queue) – struktura danych, w której elementy pobierane są z początku, a dodawane na końcu. Z kolejki można zatem pobrać tylko ten element, który był dodany najwcześniej. Kolejka bywa określana również jako kolejka FIFO (z ang. First In, First Out), w odróżnieniu od kolejki LIFO, czyli stosu.

→ Czytaj całość

Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ 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ść
Polityka prywatnościKontakt