Guruh talabasi Hamroyev Dilshodning algoritmni lohilash fanindan

106-19-guruh talabasi Hamroyev Dilshodning algoritmni lohilash fanindan

13-labaratoriya ishi.

Asosan algoritmni murakkabligini baholash uchun O simvolikadan foydalaniladi.Ya’ni ushbu baholash asosida algoritmlarni quyidagi sinflarga bo’lish mumkin.

Doimiy murakkablik n ga bog’liq emas ya’ni O(1);

Chiziqli murakkablik ya’ni O(n);

Polinimial murakkablik ya’ni O(n^m), bu yerda m konstanta ya’ni o’zgarmas son;

Eksponentsial murakkablik O(t^f(n)), bu yerda t- konstanta>1 f(n)-polinomial;

Superpolinomial murakkablik O(с^f(n)),bu yerda c-konstanta f(n)-doimiydan tezroq lekin chiziqlidan sekinroq o’sadigan funksiya hisoblanadi.

P masalalarga kelsak biz logarifmik chiziqli va polynomial murakkablikdagi masalalarni ko’rganmiz.Lekin ularni barchasini umumlashtirsak u holda ularni ko’rsatkichi logarifm birlik ba 1 dan katta qiymatlardan iborat bo’lgan polinom bilan ifodalash mumkin.Asosan bunday masalalar P-masalalar sinfiga tegishli bo’ladi.Bunday masalalar shuningdek yechilishi mumkin bo’lgan masalalar turiga kiradi.Boshqa tomondan vaqt bo’yicha murakkabligi n¹⁰⁰

yoki 10⁹⁹n2 bo’lgan polynomial algoritmlar amaliy nuqtai nazardan samarali bo’lib hisoblanmaydi.

NP masalalariga kelsak vaqt bo’yicha murakkabligi polinomial baholashga bo’ysinmaydigan algoritmlar eksponentsial algoritmlar deyiladi.Ko’pgina eksponentsial algoritmlar bu to’liq ko’rib chiqish usulining variantlari.Agar masalani yechish uchun polynomial algoritm mavjud bo’lmasa bunday masalalar qiyin yechiladigan masalalar deyiladi.Deyarli yechilmaydigan masalalar sinfi NP – determinirlanmagan polynomial murakkablikdagi sinfni ifodalaydi.Bunday masalalarni yechadigan barcha ma’lum bo’lgan determinirlangan algoritmlar murakkabligi yoki elsponentsial yoki factorial bo’ladi.NP ingliz tilida Nondeterministic Polynomial time ya’ni tarjima qilinganda determinirlanmagan polinomial vaqt degan ma’noni anglatadi. Bundan tashqari barcha P masalalar NP sinfiga ham kiradi.

Masalalar

Dastur kodi:

#include

#include

#include

using namespace std; int main()

{

int a[40],r=0,t;

srand(time(0));

int n=10;

cout<<"massivdan tasodifiy tanlangan sonlar ";

for(int i=1; i<10; i++)

a[i]=rand()%n; cout<

for(int i=1; i<10; i++)

{
cin>>t; if(a[i]==t)

{ r++;

}

}

cout<

cout<<"siz kiritgan raqamlar ichidan "<

return 0;

}