Podstawowymi miarami kosztu algorytmu są: czas i pamięć.

Jak mierzyć czas? Oczywiście chcemy by miara była niezależna od komputera, na którym realizowany będzie algorytm. Jest oczywiste, że realizacja tego samego algorytmu  na różnych komputerach dla tych samych danych, nie musi zająć tyle samo czasu. Zatem informacja, ile jednostek czasu wymaga wykonanie algorytmu dla konkretnych danych, na konkretnym komputerze, niewiele mówili o samym algorytmie. Miara kosztu algorytmu powinna zależeć od typu problemu i rodzaju rozwiązania, a nie od komputera, na którym realizujemy obliczenia. Naturalną miarą czasu może być:

* liczba instrukcji,
* liczba operacji arytmetycznych,
* liczba porównań wykonanych, w trakcie realizacji algorytmu,
* liczba wywołań rekurencyjnych procedur, itd.

W każdym algorytmie można wyróżnić pewną operację istotną dla rozwiązywanego zadania. Taką operację nazwiemy dominującą. Mówimy, że koszt czasowy algorytmów mierzymy liczbą operacji dominujących. Wybór operacji dominującej zależy od problemu i wybranego rozwiązania. W problemie mnożenia macierzy za operacje dominujące  można uznać operacje arytmetyczne +, *. W problemie wyszukiwania elementu w zbiorze, operacją dominującą jest równość. W problemie sortowania operacją dominującą jest najczęściej porównywanie elementów, ale można też przyjąć operację przestawiania elementów.

Mając dany algorytm Alg i  środowisko, w którym  będzie on pracował, możemy policzyć liczbę operacji dominujących, wykonanych przez algorytm w czasie jego realizacji dla konkretnych danych d. Liczbę tę oznaczamy przez t(Alg,d). Jeśli z kontekstu wynika o jaki algorytm chodzi, będziemy po prostu pisali t(d).

Rozważmy poznane przykłady algorytmów. W algorytmie  max, rozwiązującym problem wyszukiwania elementu największego, dane to długość ciągu i jego elementy. Wybierzmy jako operację dominującą porównywanie elementów, a rozmiar danych to liczba elementów ciągu. Dla danych d1 = <5, (1,7,4,2,8)> mamy t(max,d1) = 4, a dla danych  d2 = <6, (2,4,7,8,1,3)>,  t(max,d2)=5.

W algorytmie znajdowania pierwiastka kwadratowego z danej liczby naturalnej, rozmiarem danym może być liczba bitów potrzebnych do zapamiętania tej liczby n, a operacją dominującą operacje arytmetyczne. W każdym kroku algorytmu wykonujemy 3 operacje dodawania i jedno  badanie równości. Jeśli n=16, to t(sqrt, n) = 4 ´ 4 =16, jeśli n=25, to t(sqrt, n) = 4 ´ 5 = 20. Wiedząc jaka jest liczba wykonanych operacji dominujących, możemy dokładnie powiedzieć, ile czasu zajmie nam wykonanie algorytmu. Czy jednak jest to dla nas interesujące? Czy możemy z tych informacji wyciągnąć wniosek, ile czasu potrzeba dla wykonania algorytmu dla danych o rozmiarze 100000? Nie. 

Zupełnie inaczej wygląda sprawa, jeśli zauważymy, że np. algorytm max wykonuje zawsze n-1 porównań dla dowolnego n elementowego ciągu, a algorytm sqrt,  obliczając pierwiastek z liczby n, wykonuje zawsze 4Ön operacji arytmetycznych. Dlatego też ocenę kosztów algorytmu chcemy uniezależnić od szybkości komputera, konkretnej implementacji, języka programowania oraz konkretnego zestawu danych.  Natomiast chcemy ją uzależnić od rozmiaru danych.

To, jak mierzymy wielkość danych zależy od rozwiązywanego problemu. Na przykład, jeżeli naszym problemem jest mnożenie macierzy, to przez rozmiar danych rozumie się zwykle wymiar mnożonych macierzy; jeżeli problem polega na sortowaniu, to oczywistym rozmiarem danych jest długość sortowanego ciągu. Dla problemu wyszukiwania najkrótszych ścieżek w grafie, rozmiarem danych będzie liczba wierzchołków grafu.  Mając ustaloną operację dominującą oraz pojęcie wymiaru danych dla rozważanego algorytmu, będziemy się starali określić zależność między rozmiarem danych, a liczbą wykonanych  przez niego operacji dominujących, zwaną złożonością czasową algorytmu.

Faktyczny czas wykonania algorytmu jest proporcjonalny do jego złożoności czasowej. Znając rozmiar danych oraz złożoność algorytmu możemy wyliczyć liczbę operacji dominujących wykonywanych przez algorytm, a wiedząc na jakim komputerze algorytm zostanie wykonywany, możemy obliczyć czas potrzebny do jego wykonania.

Zdarzają się jednak algorytmy, których działanie zależy nie tylko od rozmiaru danych, ale także od ich wartości. W takich przypadkach, będziemy analizować przypadki najgorszych i średnich zachowań algorytmu.

Inną interesującą miarą złożoności algorytmu jest złożoność pamięciowa. Podobnie jak poprzednio i to pojęcie chcemy uniezależnić od komputera i języka programowania, natomiast chcemy by zależało od wymiaru danych. Miarą danych tego typu złożoności może być liczba zmiennych użytych w algorytmie lub liczba miejsc potrzebnych do zapamiętania danych. Pamiętajmy jednak, że zmienne mogą być bardzo różnych typów i w związku z tym ilość słów pamięci potrzebnych do przechowywania ich wartości różnić się może bardzo istotnie. Rozsądniej więc będzie mierzyć złożoność pamięciową ilością słów maszynowych potrzebnych do przechowania danych i realizacji algorytmu.

Złożoność pamięciową wyrażamy jako funkcję rozmiaru danych  i oznaczamy  przez S(Alg,n), gdzie Alg jest algorytmem, a n rozmiarem danych dla tego algorytmu. Podobnie jak w przypadku złożoności czasowej, ilość słów pamięci  potrzebnej do wykonania algorytmu zależy często od rodzaju danych. Rozważa się więc koszt pamięciowy pesymistyczny, oraz koszt pamięciowy średni.

W następnych wykładach tego kursu, Czytelnik pozna wiele przykładów analizy złożoności. Skupimy się jednak bardziej na analizie czasowej złożoności, niż złożoności pamięciowej przedstawianych algorytmów.

Pytanie 5 Niech Alg = {if  g then  A1 else A2 fi}, oraz tt(g) oznacza liczbę operacji dominujących wykonywanych przy badaniu testu g, a tt(A_i) - maksymalną liczbę operacji dominujących, które może wykonać algorytm A_i dla i=1,2. Jak można oszacować liczbę operacji dominujących dla algorytmu Alg?