złożoność obliczeniowa

[Edzio123]

Chciłbym zapytać jak wyznacza się zlożoność obliczeniowa i czasową algorytmów.

Np. mamy 3 sposoby mnozenia macierzy:

algorytm ijk:

Kod: [Zaznacz]

/* ijk */
for (i = 0; i < N; i++)
	for (j = 0; j < N; j++)
		for (k = 0; k < N; k++)
			C[i*N+j] += A[i*N+k]*B[k*N+j];

algorytm ikj

Kod: [Zaznacz]

for (i = 0; i < N; i++)
	for (k = 0; k < N; k++)
		for (j = 0; j < N; j++)
			C[i*N+j] += A[i*N+k]*B[k*N+j];

algorytm bikj

Kod: [Zaznacz]

for (i = 0; i < N; i+=16)
 	for (k = 0; k < N; k+=16)
 		for (j = 0; j < N; j+=16)
 			for (ii = i; ii < i+15; ii++)
 				for (kk = k; kk < k+15; kk++)
					for (jj = j; jj < j+15; jj++)
						C[ii*N+jj] += A[ii*N+kk]*B[kk*N+jj];

Wiemy, że mamy algorytmy takie jak np. O(N^2), itd. ale jak to się wyznacza?

[Paweł Kraszewski]

Wyznaczasz liczbę właściwych operacji arytmetycznych (ostatnia linijka w każdym przykładzie) w funkcji N. Jeżeli wychodzi coś bardziej złożonego, to pozostawiasz składnik najszybciej rosnący w nieskończoności i opuszczasz stałe i mnożniki. Na przykład jak wychodzi ci 5N^3 + 2N -7 to jako finalne O przyjmujesz O(N^3).

Pierwsze przykłady są zatem O(N^3), trzeci jest dokładnie O( (N/16 )^3 * 16^3 ), co w sumie daje też O(N^3).

To po co te zabawy? Jest duże prawdopodobieństwo, że trzy wewnętrzne pętle wersji bikj zmieszczą się w cache'u procesora  i to da dodatkowe przyspieszenie. ALE nie ma to związku z notacją O - w tej notacji te algorytmy są całkowicie równoważne.

[Edzio123]

Paweł, wielkie dzięki za odpowiedź.
Jednakże czy mógłbyś mi dokładniej wyjaśnić skąd bierze się postać tych funkcji? Mam namysli:
5N^3 + 2N -7  oraz (N/16 )^3 * 16^3. NIe moge tego rozkminic.

[Paweł Kraszewski]

Pierwszy wzór wziąłem "z czapy", żeby pokazać, że liczy się tylko najszybciej rosnący wyraz.

Drugi wzór (zakładem, że N jest wielokrotnością 16):
* W zewnętrznych 3 pętlach skaczesz co 16 wyraz z N. Dlatego jest (N/16)^3 obiegów.
* Dla każdego obiegu pętli zewnętrznych robisz stałe 16^3 obiegów 3 pętli wewnętrznych.
* Łącznie robisz iloczyn obu powyższych obiegów. Po wymnożeniu się pięknie redukuje do N^3