Cechy algorytmów

Podstawowymi cechami algorytmów są:

• poprawność — algorytm powinien zwracać poprawne wyniki
• jednoznaczność — algorytm powinien przy takim samym zbiorze danych wejściowych zwracać takie same wyniki
• skończoność dla każdego zbioru poprawnych danych wejściowych algorytm powinien zwracać wyniki w skończonej liczbie kroków
• efektywność algorytm powinien prowadzić do rozwiązania problemu w jak najmniejszej liczbie kroków.

Złożoność obliczeniowa algorytmu

Złożoność obliczeniowa algorytmu określa ilość zasobów (pamięci, czasu) niezbędnych do rozwiązania problemu.

• Złożoność czasowa algorytmu jest rozpatrywana jako ilość czasu potrzebnego do rozwiązania problemu w zależności od liczby danych wejściowych. Podawanie złożoności obliczeniowej w jednostkach czasu jest jednak nieprecyzyjne, bo wynik zależy również od szybkości działania komputera. Dlatego złożoność obliczeniowa algorytmu najczęściej podawana jest w liczbie wykonanych operacji i jest to największa liczba operacji dominujących wykonywanych w algorytmie dla dowolnego układu danych.

• Złożoność pamięciowa algorytmu określa wielkość pamięci operacyjnej komputera, która jest potrzebna do przechowywania danych wejściowych, danych pośrednich oraz ostatecznych wyników obliczeń.

Złożoność czasowa oraz złożoność pamięciowa algorytmu często zależą od postaci przetwarzanych danych, dlatego można je przedstawiać jako złożoność:

• pesymistyczną — określa zużycie zasobów dla najgorszego przypadku,
• oczekiwaną — określa zużycie zasobów dla uśrednionych wszystkich możliwych przypadków lub dla typowych przypadków,
• optymistyczną — określa zużycie zasobów dla najkorzystniejszego przypadku.