Algoritmi Matritsalarni ko‘paytirish dasturi

Download 88.86 Kb.

bet	3/3
Sana	18.06.2023
Hajmi	88.86 Kb.
	#1576408

1 2 3

Bog'liq
Ergashov Nuriddin

O(n) ga teng. Dastur kodi
Dastur kodi.

Algoritm	Vaqtli qiyinlik

		A1
		A2
		A3
		A4
		A5
	Faraz qilaylik, A1,A2,…,A5 nomli 5 ta algoritm quyidagi vaqtli qiyinliklar bilan berilgan. Bu yerda vaqtli qiyinlik – bu n kattalikdagi kirishlarni qayta ishlash uchun kerak bo’ladigan vaqt birliklar soni. Masalan, vaqt birligini 1 millisekund deb qabul qilaylik. Bunda A1 algoritm bir sekundda 1000 kattalikdagi kirishni qayta ishlash mumkin, A5 algoritmi esa kirish kattalikdagina 9 dan oshirib bilmaydi. Keyingi jadval 1 sekundda, 1 minutda, 1 soatda 5 ta algoritmlarni har birining yordamida yechiladigan masalaning kattaligi keltirilgan.

“O-yozuv” usulning kamchiligi shundaki – konkret berilganlar uchun dastur bajarilishiga aniq sarflanayotgan vaqtni hisoblab bilmaymiz, faqatgina qadamlar bajarilish soni bo’lganini bildik. Lekin bu usul bilan tahlil qilish qulay, va berilgan amaliy masala uchun dasturni samaradorligini aniqlaydigan dastlabki hisoblashlar uchun algoritmning izahlash vaqtini assimptotik bahosini beradi.

Samaradorlikni baholashga misollar
Masala, Qalam va qog’oz yordamida, quyidagi 16 ta kvadratdan iborat shaklni yasash kerak.

Agar biz dasturimizda bir o’lchovli massivdan foydalansak, bu kamida O(n) bilan baholanadi.

Bu yerda sikl operatori

(for(int i=0; iO(cn)=O(n). baholash bo’lganligi uchun bizning algoritmning bahosi ham O(n) ga teng.

Dastur kodi #include #include using namespace std;
double funk(double x)
{
return (1.0/(1+x*x));
}
int main()
{
double a,b,S=0, xa; int n=10;
cout<<"integral chegarasini kiriting"<>a>>b;
xa=a+0.1; while (xa{
S+=funk(xa); xa+=0.1;
} S=(a+b)/2+S;
S=S*fabs(b-a)/n; cout << S;
return 0; }

Dastur kodi.
#include
using namespace std;//ulchamlari bir xil bulgan matritsalar uchun int main()
{
int a[10][10],b[10][10],c[10][10],r,d,i,j,k;
cout<<"satrlar soni="; cin>>r; cout<<"ustunlar soni="; cin>>d;
cout<<"matritsa elementlarini kiriting=\n"; for(i=1;i<=r;i++)
{ for(j=1;j<=d;j++) {
cin>>a[i][j];} }

cout<<"ikkinchi matritsa elementlarini kiriting=\n"; for(i=1;i<=r;i++)

{ for(j=1;j<=d;j++) cin>>b[i][j];} for(i=1;i<=r;i++)
{ for(j=1;j<=d;j++)
{ c[i][j]=0;
for(k=1;k<=d;k++)
{
c[i][j]+=a[i][k]*b[k][j]; } } }
//natijani chop qilish for(i=1;i<=r;i++)
{
for(j=1;j<=d;j++)
{
cout<}
cout<<"\n";
}
return 0;
}
Bu algoritm O(n3) murakkablik bilan baholanadi. Chunki, algoritmda 3 ta ichma-ich sikl operatoridan foydalanilgan.
for(i=1;i<=r;i++)
{
for(j=1;j<=d;j++)
{ c[i][j]=0;
for(k=1;k<=d;k++)
{
c[i][j]+=a[i][k]*b[k][j];
}
}
}

Download 88.86 Kb.

Do'stlaringiz bilan baham:

1 2 3