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:

Ze względu na wykorzystane rodzaje zasobów komputerowych złożoność obliczeniową dzieli się na:

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:
Układ okresowy- kod qr
Układ okresowy

Układ okresowy pierwiastków- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play
Alkomat- wirtualny test kod qr
Alkomat- wirtualny test

Alkomat- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play
Taklarz- olinowanie stałe kod qr
Olinowanie stałe- kalkulator średnic

Olinowanie stałe- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play
przepis na gogfry

Przepis na gofry

zobacz
przepis na bitą śmietanę

Przepis na bitą śmietanę

zobacz