16-ma’ruza. Sodda parallel algoritmlar

Algoritmning 
ketma-ketligi.
Matritsa-vektorni 
ketma-ket 
koʻpaytirish algoritmini quyidagicha ifodalash mumkin. 
1-misol. Matritsani vektorga ketma-ket koʻpaytirish algoritmi 
 
for (i = 0; i < m; i++) 
{ 
c[i] = 0; 
for (j = 0; j < n; j++) 
{ 
c[i] += A[i][j]*b[j] 
} 
} 
Matritsa-vektorlarni koʻpaytirish - skalyar koʻpaytmalarni hisoblash 
ketma-ketligidir. Uzunligi n boʻlgan vektorlarning nuqta koʻpaytmasini 
har bir hisoblash n ta koʻpaytirish va n-1 qoʻshish amallarini talab 
qilganligi sababli, uning murakkabligi O (n) tartibida boʻladi. Matritsa-
vektorni koʻpaytirishni amalga oshirish uchun skalyar koʻpaytmani 
hisoblashning m ta amalini bajarish kerak, shuning uchun algoritm O (mn) 
tartibli murakkablikka ega.