Własności algorytmów
Złożoność obliczeniowa algorytmu
Złożoność obliczeniowa algorytmu określa ilość przydzielonych zasobów potrzebnych do wykonania zadanego algorytmu. Zasobami są pamięć, procesy (funkcje, metody), czas.
Wyróżnia się poniższe typy złożoności obliczeniowej:
- złożoność pesymistyczna- liczba zasobów komputerowych potrzebnych gdyby wprowadzono dane o najmniej sprzyjającym układzie
- złożoność oczekiwana- liczba zasobów komputerowych potrzebnych gdyby wprowadzono dane o sprzyjającym układzie
Ze względu na wykorzystane rodzaje zasobów komputerowych złożoność obliczeniową dzieli się na:
- złożoność czasową
- złożoność pamięciową
Złożoność czasowa
Złożoność czasowa dotyczy czasu działania algorytmu. Na jej wartość nie ma wpływu rodzaj komputera, język programowania. Mierzy się liczbę operacji dominujących wykonywanych podczas realizacji rozwiązania algorytmu. Operacjami dominującymi mogą być: porównania dwóch elementów, zamiana wyrazów ciągu, operacje przypisania, działania arytmetyczne. Jej wartość zależy od ilości wprowadzonych danych.Złożoność pamięciowa
Złożoność pamięciowa określa, ile pamięci potrzeba do realizacji danej metody. Jej wartość zależy od ilości wprowadzonych danych. Mierzy się liczbę zmiennych użytych w algorytmie ora zajmowaną przez nie pamięć.Określanie złożoności czasowej
Określanie złożoności czasowej algorytmu ustalane jest na przypisaniu postaci funkcji zależności czasu realizacji obliczeń od rozmiaru danych wejściowych. Postać funkcji szacuje czas działania algorytmu dla najmniej korzystnego (pesymistycznego) układu danych wejściowych.Złożoność czasowa jest najczęściej proporcjonalna do jednej z poniższych funkcji
Złożoność logarytmiczna (log n)
Dotyczy algorytmów, w których problem danych o rozmiarze n można sprowadzić do stałej liczby operacji dominujących do problemu o rozmiarze n/2 (przykład algorytm przeszukiwania binarnego ciągu uporządkowanego). Symbol zapisu: O(log n)Złożoność liniowa (n)
Dotyczy algorytmów, dla których każda dana wejściowa poddana jest stałej liczbie operacji wejściowych (przykład algorytm wyznaczania wartości wielomianu według schematu Hornera). Symbol zapisu: O(n)Złożoność liniowo- logarytmiczna (n log n)
Dotyczy algorytmów, dla których problem przypisany dla danych o rozmiarze n da się przedstawić w liniowej liczbie operacji dwóch problemów o rozmiarze n/2 (przykład algorytm sortowania przez scalanie). Symbol zapisu: O(n log n)Złożoność kwadratowa (n2)
Dotyczy algorytmów, dla których w każdej parze danych wejściowych realizowane są operacje dominujące (przykład wykonywanie działań dla wszystkich elementów tablicy dwuwymiarowej). Symbol zapisu: O(n2)Złożoność wykładnicza (2n)
Dotyczy algorytmów, dla których liczba operacji dominujących wykonywana jest dla każdego podzbioru danych wejściowych rozmiaru n (przykład algorytm wieża Hanoi). Symbol zapisu: O(2n)Złożoność wykładnicza (n!)
Dotyczy algorytmów, dla których liczba działań dominujących wykonywana jest dla każdej permutacji (czyli dowolny ciąg n- wyrazowy utworzony ze wszystkich elementów tego zbioru) danych wejściowych rozmiaru n (przykład wyszukiwanie wszystkich anagramów podanego słowa o długości n znaków). Symbol zapisu: O(n!)Poprawność i skończoność algorytmów
Algorytm jest poprawny, jeżeli dla każdego układu danych wejściowych zgodnych ze specyfikacją spełnia następujące warunki:- jest skończony
- otrzymane wyniki są zgodne z warunkami specyfikacji
- jest uniwersalny
- jest optymalny
