Reja Algoritmlar va ularning to’liq tuzulishining bosqichlari

Xoara algoritmini rekursiv usulda amalga oshirish

Quyidagi dastur rekursiv prosedurani qo’llaydi.

Prosedure Hoare;
Prosedure sort (L, R: index);
var i, j: index; w, x: item;
begin i:=L; j:=R; x:=a[(L+R) div 2];
repeat
while a[i]while a[j]>x do j:=j+1 end;
if i<=j then
begin w:=a[i]; a[i]:=a[j]; a[j]:=w;
i:=i+1; j:=j-1; end;
until i>j
if Lif iend {*sort*};
begin sort (1, n);
end {* Hoare*};
Norekursiv dasturni tuzish uchun yordamchi steklardan foydalaniladi.
Algoritmni baholash

Xoara algoritmni unumdorligini tahlil qilamiz. Boshlab bo’linish jarayonini ko’raylik. Qandaydir x ni tanlab biz massivni to’liq o’tamiz. Demak, n ta taqqoslashni amalga oshiramiz. Taqqoslashlarni umumiy soni n*log(n) ekanligi, o’rin almashtirishlar soni esa ekanligi isbotlangan.

Bizning misolimizda x - o’rtancha element deb tanlangan, lekin Xoara fikri bo’yicha X ixtiyoriy tanlanishi kerak. Xoara algoritmning o’rtacha ishlash vaqti teng.


5.MATRISALARNI KO’PAYTIRISH UCHUN SHTRASSEN ALGORITMI

Matrisalarni ko’paytirishda assimptotik hisoblash murakkabligini tahlil qilamiz. Oddiy O(n³) murakkabligiga ega algoritmni assimptotik yahshilash jarayonini o’rganamiz va 2 ta matrisalarni ko’paytirishda O(n^2,81) vaqt yetarli ekanligini ko’rsatamiz.

Ikkita o’lchamli A va B matrisalar berilgan bo’lsin. Bu yerda n - 2 ning darajasidagi son deb qabul qilinadi. A va B matrisalarni 4 ta o’lchamli matrisalarga bo’lish mumkinligi haqidagi lemmani qo’llab, A va B larni ko’paytmasini quyidagicha tasvirlaymiz.



Bu yerda
A₁₁ – yuqori chap kvadrat,
A₁₂ – yuqori o’ng kvadrat,
A₂₁ – pastki chap kvadrat,
A₂₂ – pastki o’ng kvadrat.
Shtrassen 2 ta o’lchamli matrisalarni ko’paytirish uchun sun’iy usulni ishlab chiqqan. Bu usulda 7 ta ko’paytirish amalga oshiriladi. Usulni rekursiv qo’llab, 2 ta matrisani vaqtda ko’paytiriladi. .