Poznaliśmy już definicję algorytmów i ich przykładowe zapisy.

Jednoznaczność algorytmu

Każdy algorytm, musi być jasno określonym ciągiem poleceń. Jeśli polecenia są jasno zdefiniowane, to powinny być również jednoznaczne.

To właśnie jednoznaczność jest jedną z cech każdego algorytmu. Cecha ta nazywana jest również określonością.

Jednoznaczność algorytmu gwarantuje, że dla tych samych danych wejściowych otrzymamy taki sam wynik. Warto zaznaczyć, że istnieją algorytmy, które w różnym stopniu realizują optymalnośćoptymalnośćoptymalność, w zakresie swojej implementacji. Przez co wyniki poszczególnych implementacji mogą się od siebie różnić. Jednak prawidłowa implementacja algorytmu zwróci poprawny wynik.

Skończoność algorytmu

Lista kroków musi w każdym algorytmie doprowadzać do jego zakończenia i powinna się wykonać w skończonej liczbie kroków (własność stopu).

Poprawność algorytmu

Algorytm jest całkowicie poprawny względem warunków początkowego i końcowego, gdy dla wszystkich danych zgodnych ze specyfikacją obliczenia algorytmu kończą się i wyniki spełniają warunek końcowy.

Przykładowo, chcemy ugotować zupę (np. krupnik) według przepisu (algorytmu). Przygotowujemy niezbędne składniki i wykonując kolejne kroki zgodnie z przepisem, otrzymujemy krupnik. Problem powstałby w sytuacji, gdybyśmy dysponując tym przepisem, chcieli ugotować rosół, a nie krupnik. Nie udalibyśmy się przecież do twórcy przepisu na krupnik, twierdząc, że jego przepis jest błędny.

A zatem o ile rosół w przypadku przepisu byłby poprawnym wynikiem, to nie byłby wynikiem przez nas oczekiwanym, co jednak wcale nie skreśla tego przepisu jako poprawnego.

Pamiętajmy więc, że nawet jeśli algorytm będzie poprawny, może z jakiegoś powodu nie spełnić naszych oczekiwań – choćby właśnie dlatego, że użyjemy nie tego algorytmu, którego potrzebowaliśmy.

Adekwatność algorytmu

Jednakże, gdyby ktoś określił przepis na rosół jako przepis na krupnik, to algorytm ten byłby błędny, ponieważ nie realizowałby założonego przez nas celu.
Własność ta nazywana bywa również adekwatnością – właśnie ze względu na to, że wynik powinien być zgodny z przyjętym celem.

Innym powodem, dla którego powyższą własność nazywa się czasem adekwatnością, jest to, że aby algorytm był poprawny, musi spełniać konkretne warunki. Dlatego też powiedzenie, że „algorytm nie jest poprawny, ponieważ nie spełnia własności poprawności”, może się wydawać nie do końca intuicyjne i być uznane za pleonazm. Musimy to wyraźnie podkreślić: własność poprawności a poprawność algorytmu to nie jest to samo. Warto o tym pamiętać, ponieważ istnieją pojęcia związane z  poprawnością, częściową poprawnością oraz niepoprawnością algorytmu, które będziemy omawiać w dalszej części lekcji.

Złożoność algorytmu

Bardzo ważną cechą algorytmu jest jego złożoność, czasami nazywana też efektywnością. Każdy algorytm ma pewną złożoność obliczeniową i pamięciową.

Złożoność pamięciowa oznacza, ile komórek pamięci zajmie dany algorytm. Z racji tego, że algorytmy są uniwersalne, zwraca się uwagę jedynie na to, ile komórek pamięci zajmują elementy zdefiniowane przez algorytm, bez uwzględnienia tego, co dodatkowo wykorzystuje sam język.

Złożoność obliczeniowa liczona jest na podstawie liczby operacji dominujących, wykonywanych w trakcie tego algorytmu. Operacja dominująca to taka, która jest realizowana w algorytmie najczęściej. Nie śledzi się więc wszystkich operacji, a jedynie te dominujące.

W przypadku algorytmów można podawać trzy różne złożoności:

• pesymistyczne,

• średnie,

• optymistyczne.

Do zapisywania złożoności używa się notacji wielkiego $\text O$, omegi $\Omega$ lub thety $\Theta$.

Słownik