Niech P będzie ustalonym problemem, a K klasą wszystkich algorytmów rozwiązujących ten problem (rozważamy tu wszystkie algorytmy, nawet jeśli ich wszystkich nie znamy), stosując ten sam typ operacji dominujących oraz ten sam ustalony typ organizacji danych. Chcemy poznać najlepszy, tzn. najmniej kosztowny, algorytm tej klasy rozwiązujący problem P.

Definiujemy złożoność optymalną klasy K, jako kres dolny złożoności algorytmów z tej klasy. Powiemy, że algorytm Alg jest optymalny w klasie K, jeżeli jego złożoność jest równa złożoności optymalnej.

W konsekwencji algorytm Alg z klasy K jest optymalny, jeżeli nie istnieje w tej klasie algorytm Alg' rozwiązujący problem P zużywając mniej operacji dominujących niż Alg.

Rozważmy problem znalezienia elementu najmniejszego w danym zbiorze. Danymi do tego algorytmu jest skończony ciąg x elementów dowolnej liniowo uporządkowanej przestrzeni oraz jego długość n.

min{
	result := x₁; i := 2;
	while (i £ n) do
	if not (result £ x_i) then result := x_i fi;
	i := i+1
	od
}

Niech K będzie teraz klasą wszystkich algorytmów rozwiązujących problem znajdowania minimum ciągu przez porównywanie elementów. Nasz algorytm min, dla ciągu n elementowego, wykonuje dokładnie n-1 porównań. Czy w klasie K znajdzie się algorytm wykonujący mniej porównań? Twierdzimy, że w każdym algorytmie klasy K, każdy element różny od minimalnego musi być co najmniej raz porównany z elementem minimalnym. Przypuśćmy, że tak nie jest, tzn. przypuśćmy, że w klasie K istnieje taki algorytm min*, który znajduje element minimalny MIN bez porównywania go np. z elementem na pozycji i0. Zmodyfikujmy dane do tego algorytmu, tak by na pozycji i0 znalazł się jakiś element mniejszy od MIN. Algorytm min* dla takich danych nie da poprawnego wyniku. Nie może więc należeć do rozważanej klasy K.

Wniosek: Algorytm min jest optymalnym rozwiązaniem problemu znajdowania elementu najmniejszego ciągu przez porównywanie elementów. Złożoność optymalna dla tego problemu wyraża się funkcją T(n) = n-1.

Dla wielu problemów nie możemy określić dokładnie złożoności optymalnej, ale za to można ustalić jej rząd wielkości. W takim przypadku, algorytm A klasy K jest optymalny, jeśli jego złożoność ma rząd mniejszy bądź równy złożoności wszystkich innych algorytmów tej klasy. Oczywiście w klasie K może być wiele różnych algorytmów optymalnych.

W tym cyklu wykładów przedstawimy kilka przykładów problemów, dla których znane są optymalne algorytmy rozwiązywania. Na ogół są to zadania bardzo trudne i wiele problemów nadal czeka na swoje najlepsze rozwiązanie.

Rozważmy problem mnożenia macierzy. Dane są dwie macierze A i B, odpowiednio rozmiarów (n×u) i (u'×m). Znaleźć macierz C = A×B. Niech elementy macierzy A, B, C będą oznaczone odpowiednio przez a[i,j], b[i,j], c[i,j]. Specyfikacja algorytmu rozwiązującego ten problem może mieć postać następujących warunków:

wp = {u'=u}, wk = {c[i,j] = S{a[i,k] ´ b[k,j]:1 £ k £ u} dla i=1,...,n, j=1,...,m}.

Dla uproszczenia, załóżmy że rozważamy macierze o elementach rzeczywistych. Jako operację dominującą przyjmiemy operację mnożenia liczb rzeczywistych.

Rozwiązanie 1: Pierwsze rozwiązanie wykorzystuje wprost definicję mnożenia macierzy.

MnM_1{
	for i := 1 to n do
	for j := 1 to m do
	c[i,j] := 0;
	for k := 1 to u do
	c[i,j] := c[i,j] + a[i,k] ´ b[k,j]
	od
	od od}

Koszt czasowy tego algorytmu mierzony ilością mnożeń wyraża się funkcją T(n,m,u) = n´m´u. Koszt pamięciowy natomiast wyraża się funkcją S(n,m,u) = n ´ u + m ´ u + n ´ m. Jeśli przyjmiemy, że m = u = O(n), wtedy asymptotyczna złożoność czasowa i pamięciowa wyrażają się odpowiednio przez funkcje

Idea tego algorytmu polega na podzieleniu zadania na podzadania. Załóżmy, że n = m = u = 2^k. Macierze A i B można przedstawić jako macierz (2×2) o elementach będących macierzami o wymiarach (n/2×n/2). Oznaczmy te części macierzy A przez A_11,A₁₂, A₂₁,A₂₂. Analogicznie są zdefiniowane elementy macierze B_ij.

Wtedy iloczyn C macierzy A i B może być przedstawiony również jako macierz (2×2) o elementach C_ij będących macierzami o wymiarach (n/2×n/2). Macierze C_ij dla i,j=1,2 można wyliczyć korzystając z definicji mnożenia macierzy (2×2):

C₁₁ = A₁₁ ´ B₁₁+ A₁₂ ´ B₂₁ C₁₂ = A₁₁ ´ B₁₂ + A₁₂ ´ B₂₂
C₂₁ = A₂₁ ´ B₁₁+ A₂₂ ´ B₂₁ C₂₂ = A₂₁ ´ B₁₂ + A₂₂ ´ B₂₂

Proste sprawdzenie dowodzi, że tak otrzymana macierz C jest iloczynem macierzy oryginalnych A i B.

Przedstawiony poniżej algorytm rekurencyjny wykorzystuje pomysł dzielenia macierzy, które chcemy pomnożyć, na cztery części, tak długo aż otrzymamy macierzy jednoelementowe. Aby uniknąć tworzenia macierzy pomocniczych w każdym wywołaniu rekurencyjnym procedury, wyniki pośrednie będą od razu zapisywane w wynikowej tablicy C. Otrzymamy w ten sposób następujący algorytm:

MnRek	(n,i,j,k,l: int){
	if n>1 then
	MnRek(n/2, i, j ,k, l);	// C_il := A_ij ´ B_kl
	MnRek(n/2, i, j+n/2, k+n/2,l);	// C_il := A_ij ´ B_kl+ A_i(j+n/2) ´ B_(k+n/2)l
	MnRek(n/2, i, j, k, l+n/2);	// C_i(l+n/2) := A_ij ´ B_k(l+n/2)
	MnRek(n/2, i, j+n/2, k+n/2, l+n/2);	// C_i(l+n/2) := A_ij ´ B_k(l+n/2)+ A_i(j+n/2) ´ B_{(k+n/2)(l+n/2)}
	MnRek(n/2, i+n/2, j, k, l);	// C_(i+n/2)l := A_(i+n/2)j ´ B_kl
	MnRek(n/2, i+n/2, j+n/2, k+n/2, l);	// C_(i+n/2)l := A_(i+n/2)j ´ B_kl+ A_{(i+n/2)(j+n/2)} ´ B_(k+n/2)l
	MnRek(n/2, i+n/2, j, k, l+n/2);	// C_{(i+n/2)(l+n/2)} := A_(i+n/2)j ´ B_k(l+n/2)
	MnRek(n/2, i+n/2, j+n/2, k+n/2, l+n/2);	//C_{(i+n/2)(l+n/2)} := A_(i+n/2)j ´ B_k(l+n/2)+ A_{(i+n/2)(j+n/2)} ´ B_{(k+n/2)(l+n/2)}
	else
	C[i,l] := C[i,l] + A[i,j] ´ B[k,l]
	fi}

Parametry i, j określają lewy górny róg tego fragmentu macierzy A, a parametry k, l - lewy górny róg tego fragmentu macierzy B, które mają zostać pomnożone. Parametr n mówi o wymiarze mnożonych macierzy. Algorytm wywołany dla parametrów (2^k, 1, 1, 1, 1) daje poprawne wyniki, przy założeniu, że początkowe wartości w tablicy C są zerami.

Przeanalizujmy koszt związany z realizacją tego algorytmu. Niech M(k) będzie liczbą mnożeń liczb rzeczywistych wykonanych przez algorytm MnRek dla rozwiązania zadania o rozmiarze n = 2^k. Jeśli mnożone tablice mają tylko po jednym elemencie, to algorytm wykona tylko jedno mnożenie rzeczywiste. Jeśli n>1, to wykonujemy 8 mnożeń macierzy dwa razy mniejszych. Stąd równanie rekurencyjne opisujące funkcję M(k):

Niestety nie widać poprawy w stosunku do poprzedniego algorytmu. Jednak idea zawarta w tym algorytmie pozwoliła zaprojektować inny, i jak się okazało teoretycznie lepszy, algorytm mnożenia macierzy.

Strassen zauważył, że kosztem większej liczby dodawań, mnożenie macierzy (2×2) można zrealizować wykonując tylko 7 mnożeń, a nie jak dotychczas 8. Łącząc pomysł Strassena i ideę dzielenia dużych macierzy na 4 części (zakładamy ponownie, że n=2^k), tak jak w algorytmie MnRek, otrzymamy inny rekurencyjny algorytm, nazwijmy go Strassen, dla którego liczbę wykonanych mnożeń opisuje funkcja M(Strassen, k):

Rozwiązaniem tego równania rekurencyjnego jest funkcja T(Strassen,k) = 7^k , czyli ostatecznie T(Strassen,n) = 7^{lg n} = n^{lg 7}.

Złożoność czasowa algorytmu Strassena jest więc mniejsza niż pozostałych, co więcej rząd wielkości funkcji T(Strassen,n) jest istotnie mniejszy niż n³. Powstaje pytanie, czy istnieje algorytm wykonujący mniej mnożeń niż algorytm Strassena?
Wiadomo, że każdy algorytm mnożenia macierzy n×n musi wykonać co najmniej n² mnożeń, tzn. złożoność czasowa każdego algorytmu rozwiązującego problem mnożenia macierzy jest T(n) = W(n²). Nie znamy jednak żadnego algorytmu, który realizuje to ograniczenie dolne. Problem znalezienia algorytmu optymalnego dla problemu mnożenia macierzy jest ciągle otwarty.