Menu Zamknij

Algorytmy

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