Algorytm – skończony ciąg jasno zdefiniowanych czynności koniecznych do wykonania pewnego rodzaju zadań, sposób postępowania prowadzący do rozwiązania problemu
- algorytmy numeryczne (matematyczne) – mają za zadanie wykonywać obliczenia arytmetyczne
- algorytmy przeszukujące – maja za zadanie badanie zbioru w celu wyszukania wskazanego elementu,
- algorytmy porządkujące – ustawiają elementy danego zbioru w wymaganej kolejności,
- algorytmy rekurencyjne – rozwiązują problemy, które da się podzielić na mniejsze części, stanowiące kopie wzorca,
- algorytmy szyfrujące – zmieniają dane tak, by ich odczyt nie był możliwy bez znajomości klucza kodującego,
- algorytmy kompresji danych – określają taki sposób zapisu danych, by zmniejszyć objętość pliku kompresowanego
Złożoność obliczeniowa, nazywana też czasową , określa ilość zasobów potrzebnych do rozwiązania problemów obliczeniowych. Zasobami, które są brane pod uwagę mogą być następujące: czas, pamięć lub liczba procesorów.
Wybrane klasy złożoności obliczeniowej
| Złożoność czasowa | Opis | Szybkość |
|---|---|---|
| O(1) | stała złożoność – algorytm wykonuje się w stałej ilości operacji, niezależnie od liczby danych wejściowych. | działa prawie natychmiast |
| O(log2(n)) | złożoność logarytmiczna – algorytm wykonuje logarytmiczną ilość operacji w stosunku do liczby danych wejściowych. *n jest to liczba danych wejściowych; |
bardzo szybki |
| O(n) | złożoność liniowa – algorytm wykonuje wprost proporcjonalną ilość operacji do liczby danych wejściowych. | szybki |
| O(n*log2(n)) | złożoność liniowo-logarytmiczna | szybki |
| O(n2) | złożoność kwadratowa – ilość operacji algorytmu jest wprost proporcjonalna do liczby danych wejściowych podniesionej do potęgi drugiej. | wolny dla dużych n |
| O(nX) | złożoność wielomianowa – ilość operacji algorytmu jest wprost proporcjonalna do liczby danych wejściowych podniesionej do potęgi X. | wolny dla większych n |
| O(Xn) | złożoność wykładnicza – ilość operacji algorytmu jest wprost proporcjonalna do stałej X większej lub równej 2, podniesionej do potęgi równej liczbie danych wejściowych. | możliwy do niewykonania dla większych n |