Treść artykułu powstała przy pomocy skryptu stworzonego przez Panią Dr. Jolantę Koszelew z Politechiniki Białostockiej.

Def:
    Analiza algorytmów to dział informatyki zajmujący się szukaniem najefektywniejszych, poprawnych algorytmów dla danych problemów komputerowych.

----Poprawność całkowita i częściowa algorytmu-----

WP - warunek początkowy - formuła logiczna definiująca dane wejściowe algorytmu.

WK - warunek końcowy - formuła logiczna definiująca dane wyjściowe algorytmu uzyskane dla danych wejściowych spełniających WP.


Def:
    Algorytm A jest częściowo poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP, jeżeli algorytm A zatrzymuje się, to dane wyjściowe algorytmu spełniają warunek WK.

Def:
    Algorytm A jest całkowicie poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP algorytm A zatrzymuje się i dane wyjściowe tego algorytmu spełniają warunek WK.

Też nie przepadam za regółkami i definicjami.. dlatego poniżej zamieszczam przykład.
( Wyjasnienie -> slowa w niawiasach oznaczaja symbole logiczne stosowane w matematyce ktorych nie da sie wyswietlic na stronie).

WP: n>0 ^ n(należy do)N
WK: s=1+3+5+...+n n mod 2(różne od)0(lub) s=1+3+5+...+n-1 ^ n mod 2=0

Algorytm:
kods:=0; i:=1;
while i<>n+2 do
begin
    s:=s + i;
    i:=i+2;
end
    Algorytm jest poprawny częściowo, ale nie całkowicie. Dla n parzystego pętla nie ma stopu, ale dla dowolnego n nieparzystego pętla kończy się po skończonej liczbie kroków i wartość końcowa zmiennej s spełnia WK.

------ Złożoność obliczeniowa algorytmu -------

    Złożoność obliczeniowa algorytmu to nic innego jak ilość zasobów komputerowych, potrzebnych do jego wykonania. Zasoby komputerowe natomiast to czas działania i ilość zajmowanej pamięci.

d - dane wejściowe algorytmu, czyli takie, które spełniają warunek WP.
|d|- rozmiar danych d
Przykład:
A1:
WP: a1, a2, ..., an- ciąg liczb całkowitych (n >0)
WK: Ciąg a1, a2, ..., an posortowany niemalejąco
d - ciąg a1, a2, ..., an liczb całkowitych (n >0)
|d| - n

A2:
WP: a0, a1, ..., an- ciąg liczb rzeczywistych (n >= 0) definiujący współczynniki danego wielomianu W, x- dana liczba rzeczywista
WK: Liczba W(x) &#8211; wartość wielomianu W dla argumentu x
d - ciąg a0, a1, ..., an , ciąg liczb rzeczywistych (n >= 0) definiujący współczynniki danego wielomianu W
|d|- n+1

A3:
WP: t1, t2, ..., tn- ciąg znaków tekstu (n > 0)
w1, w2, ..., wm - ciąg znaków wzorca (n >= m > 0)
WK: p - zmienna logiczna przyjmuje wartość true, gdy wzorzec występuje w tekście, a false, gdy wzorzec nie występuje w tekście.
d - t1, t2, ..., tn- ciąg znaków tekstu (n > 0)
w1, w2, ..., wm - ciąg znaków wzorca (n >= m > 0)
|d|- n, m

Def :
    Operacja elementarna (inaczej operacja dominująca) to operacja charakterystyczna dla danego algorytmu. To taka operacja, że łączna ich liczba jest proporcjonalna do liczby wykonań wszystkich operacji jednostkowych w dowolnej komputerowej realizacji algorytmu.

Przykłady:

A1 - operacją elementarną jest operacja porównywania elementów sortowanego ciągu albo operacja przestawiania elementów ciągu w czasie sortowania.

A2 - operacją elementarną jest operacja arytmetyczna mnożenia albo operacja arytmetyczna dodawania realizowana w procesie obliczania wartości wielomianu dla danego x.

A3 - operacja porównywania znaków wzorca ze znakami tekstu w procesie sprawdzania, czy wzorzec występuje w tekście.

Za jednostkę złożoności czasowej przyjmuje się wykonanie jednej operacji elementarnej (dominującej). Złożoność czasowa algorytmu jest funkcją rozmiaru danych.

-------Złożoność czasowa średnia i pesymistyczna--------

cdn...