O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI
KOMPYUTER INJINERING FAKULTETI
Algoritm va matematik modellashtirish kafedrasi
ALGORITMNI LOYIHALASH FANIDAN
MUSTAQIL ISH
Guruh : CAL 009
Bajardi : Abdukarimov M
Tekshirirdi : Begimov O’ktamjon
Toshkent 2023
MAVZU : Algoritm murakkabligini statik va dinamik o’lchovlari. Vaqt va xotira hajmi bo’yicha qiyinchiliklar
REJA :
1 Algaritmning turlari va xossalari
2 Algaritimning vaqt murakkabligini baholash
3 Algaritimlarni vaqt va hajmiy murakkabligini baholash
4 Algaritim murakkabligi
Foydalanilgan adabiyotlar
1 Algaritmning turlari va xossalari elementlarining yig‘indisini hisoblash masalasini qaraylik.
Bu yig‘indi hisoblash uchun, i ning har bir qiymatida j bo‘yicha ko‘paytmani hisoblab, avval yig‘indi ustiga ketma-ket qo‘shib borish kerak bo‘ladi. Bu jarayon quyidagi blok–sxemada aks ettirilgan. Bu yerda i-tashqi sikl - yig‘indi uchun, j-esa ichki sikl-ko‘paytmani hosil qilish uchun foydalanilgan.
Ichma-ich joylashgan siklik algoritmga doir blok-sxema
Yuqorida qayd qilganimizdek, qo‘yilgan biror masalani EHMda yechish uchun, avval uning matematik modelini, keyin algoritmini va programmasini tuzish kerak bo‘ladi. Bu uchlikda algoritm bloki muhim ahamiyatga ega. Endi algoritm tushunchasining ta’rifi va xossalarini bayon qilamiz.
Algoritm bu oldimizga qo‘yilgan masalani yechish zarur bo‘lgan amallar ketma-ketligidir.
Algoritm so‘zi va tushunchasi IX asrda yashab ijod etgan buyur alloma Muhammad al-Xorazmiy nomi bilan uzviy bog‘liq. Algoritm so‘zi Al-Xorazmiy nomini Yevropa olimlari tomonidan buzib talaffuz qilinishidan yuzaga kelgan. Al-Xorazmiy birinchi bo‘lib o‘nlik sanoq sistemasining tamoyillarini va undagi to‘rtta amallarni bajarish qoidalarini asoslab bergan.
Algoritmning asosiy xossalari.Algoritmning 5-ta asosiy xossasi bor:
Diskretlilik (Cheklilik). Bu xossaning mazmuni algoritmlarni doimo chekli qadamlardan iborat qilib bo‘laklash imkoniyati mavjudligida. Ya’ni uni chekli sondagi oddiy ko‘rsatmalar ketma-ketligi shaklida ifodalash mumkin. Agar kuzatilayotgan jarayonni chekli qadamlardan iborat qilib qo‘llay olmasak, uni algoritm deb bo‘lmaydi.
Tushunarlilik. Biz kundalik hayotimizda berilgan algoritmlar bilan ishlayotgan elektron soatlar, mashinalar, dastgohlar, kompyuterlar, turli avtomatik va mexanik qurilmalarni kuzatamiz.
Ijrochiga tavsiya etilayotgan ko‘rsatmalar, uning uchun tushinarli mazmunda bo‘lishi shart, aks holda ijrochi oddiygina amalni ham bajara olmaydi. Undan tashqari, ijrochi har qanday amalni bajara olmasligi ham mumkin.
Har bir ijrochining bajarishi mumkin bo‘lgan ko‘rsatmalar yoki buyruqlar majmuasi mavjud, u ijrochining ko‘rsatmalar tizimi (sistemasi) deyiladi. Demak, ijrochi uchun berilayotgan har bir ko‘rsatma ijrochining ko‘rsatmalar tizimiga mansub bo‘lishi lozim.
Ko‘rsatmalarni ijrochining ko‘rsatmalar tizimiga tegishli bo‘ladigan qilib ifodalay bilishimiz muhim ahamiyatga ega. Masalan, quyi sinfning a’lochi o‘quvchisi "son kvadratga oshirilsin" degan ko‘rsatmani tushinmasligi natijasida bajara olmaydi, lekin "son o‘zini o‘ziga ko‘paytirilsin" shaklidagi ko‘rsatmani bemalol bajaradi, chunki u ko‘rsatma mazmunidan ko‘paytirish amalini bajarish kerakligini anglaydi.
Aniqlik. Ijrochiga berilayotgan ko‘rsatmalar aniq mazmunda bo‘lishi zarur. Chunki ko‘rsatmadagi noaniqliklar mo‘ljaldagi maqsadga erishishga olib kelmaydi. Odam uchun tushinarli bo‘lgan "3-4 marta silkitilsin", "5-10 daqiqa qizdirilsin", "1-2 qoshiq solinsin", "tenglamalardan biri yechilsin" kabi noaniq ko‘rsatmalar robot yoki kompyuterni qiyin ahvolga solib qo‘yadi.
Bundan tashqari, ko‘rsatmalarning qaysi ketma-ketlikda bajarilishi ham muhim ahamiyatga ega. Demak, ko‘rsatmalar aniq berilishi va faqat algoritmda ko‘rsatilgan tartibda bajarilishi shart ekan.
Ommaviylik. Har bir algoritm mazmuniga ko‘ra bir turdagi masalalarning barchasi uchun ham o‘rinli bo‘lishi kerak. YA’ni masaladagi boshlang‘ich ma’lumotlar qanday bo‘lishidan qat’iy nazar algorim shu xildagi har qanday masalani yechishga yaroqli bo‘lishi kerak. Masalan, ikki oddiy kasrning umumiy mahrajini topish algoritmi, kasrlarni turlicha o‘zgartirib bersangiz ham ularning umumiy mahrajlarini aniqlab beraveradi. Yoki uchburchakning yuzini topish algoritmi, uchburchakning qanday bo‘lishidan qat’iy nazar, uning yuzini hisoblab beraveradi.Natijaviylik. Har bir algoritm chekli sondagi qadamlardan so‘ng albatta natija berishi shart. Bajariladigan amallar ko‘p bo‘lsa ham baribir natijaga olib kelishi kerak. Chekli qadamdan so‘ng qo‘yilgan masala yechimga ega emasligini aniqlash ham natija hisoblanadi. Agar ko‘rilayotgan jarayon cheksiz davom etib natija bermasa, uni algoritm deb atay olmaymiz.
Algoritmning tasvirlash usullari .Yuqorida ko‘rilgan misollarda odatda biz masalani yechish algoritmini so‘zlar va matematik formulalar orqali ifodaladik. Lekin algoritm boshqa ko‘rinishlarda ham berilishi mumkin. Biz endi algoritmlarning eng ko‘p uchraydigan turlari bilan tanishamiz.
1.Algoritmning so‘zlar orqali ifodalanishi. Bu usulda ijrochi uchun beriladigan har bir ko‘rsatma jumlalar, so‘zlar orqali buyruq shaklida beriladi.
2. Algoritmning formulalar bilan berilish usulidan matematika, fizika, kimyo kabi aniq fanlardagi formulalarni o‘rganishda foydalaniladi. Bu usulni ba’zan analitik ifodalash deyiladi.
3. Algoritmlarning grafik shaklida tasvirlanishida algoritmlar maxsus geometrik figuralar yordamida tasvirlanadi va bu grafik ko‘rinishi blok-sxema deyiladi.
4. Algoritmning jadval ko‘rinishda berilishi. Algoritmning bu tarzda tasvirlanishdan ham ko‘p foydalanamiz. Masalan, maktabda qo‘llanib kelinayotgan to‘rt xonali matematik jadvallar yoki turli xil lotereyalar jadvallari. Funksiyalarning grafiklarini chizishda ham algoritmlarning qiymatlari jadvali ko‘rinishlaridan foydalanamiz. Bu kabi jadvallardan foydalanish algoritmlari sodda bo‘lgan tufayli ularni o‘zlashtirib olish oson.
Yuqorida ko‘rilgan algoritmlarning tasvirlash usullarining asosiy maqsadi, qo‘yilgan masalani yechish uchun zarur bo‘lgan amallar ketma-ketligining eng qulay holatinni aniqlash va shu bilan odam tomonidan programma yozishni yanada osonlashtirishdan iborat. Aslida programma ham algoritmning boshqa bir ko‘rinishi bo‘lib, u insonning kompyuter bilan muloqotini qulayroq amalga oshirish uchun mo‘ljallangan.Blok-sxemalarni tuzishda foydalaniladigan asosiy sodda geometrik figuralar quyidagilardan iborat:Blok-sxemalar bilan ishlashni yaxshilab o‘zlashtirib olish zarur, chunki bu usul algoritmlarni ifodalashning qulay vositalaridan biri bo‘lib programma tuzishni osonlashtiradi, programmalash qobiliyatini mustahkamlaydi. Algoritmik tillarda blok - sxemaning asosiy strukturalariga maxsus operatorlar mos keladi.Shuni aytish kerakni, blok-sxemalardagi yozuvlar odatdagi yozuvlardan katta farq qilmaydi.Misol sifatida ax2+bx+c=0 kvadrat tenglamani yechish algoritmining blok-sxemasi quyida keltirilgan.Blok-sxemalar bilan ishlashni yaxshilab o‘zlashtirib olish zarur, chunki bu usul algoritmlarni ifodalashning qulay vositalaridan biri bo‘lib programma tuzishni osonlashtiradi, programmalash qobiliyatini mustahkamlaydi. Algoritmik tillarda blok - sxemaning asosiy strukturalariga maxsus operatorlar mos keladi.
Shuni aytish kerakni, blok-sxemalardagi yozuvlar odatdagi yozuvlardan katta farq qilmaydi.
Misol sifatida ax2+bx+c=0 kvadrat tenglamani yechish algoritmining blok-sxemasi quyida keltirilgan.
Chiziqli algoritmlar.Har qanday murakkab algoritmni ham uchta asosiy struktura yordamida tasvirlash mumkin. Bular ketma-ketlik, ayri va takrorlash strukturalaridir. Bu strukturalar asosida chiziqli, tarmoqlanuvchi va takrorlanuvchi hisoblash jarayonlarining algoritmlarini tuzish mumkin. Umuman olganda, algoritmlarni shartli ravishda quyidagi turlarga ajratish mumkin:
Faqat ketma-ket bajariladigan amallardan tashkil topgan algoritmlarga-chiziqli algoritmlar deyiladi. Bunday algoritmni ifodalash uchun ketma-ketlik strukturasi ishlatiladi. Strukturada bajariladigan amal mos keluvchi shakl bilan ko‘rsatiladi. Chiziqli algoritmlar blok-sxemasining umumiy strukturasini quyidagi ko‘rinishda ifodalash mumkin:
Yuqorida keltirilgan algoritm va blok sxemadan ko‘rinib turibdiki amallar ketma-ketligining ma’lum qismi parametr i ga nisbatan N marta takrorlanayapti.
Yuqorida ko‘rilgan yig‘indi blok sxemalaridagi takrorlanuvchi qismlariga (aylana ichiga olingan) quyidagi sharti keyin berilgan siklik struktura mos kelishini ko‘rish mumkin. Yuqoridagi blok sxemalarda shartni oldin tekshiriladigan holatda chizish mumkin edi. Masalan, yig‘indining algoritmini qaraylik. Bu blok sxemaning takrorlanuvchi qismiga quyidagi, sharti oldin berilgan siklik strukturaning mos kelishini ko‘rish mumkin. 1 dan n gacha bo‘lgan sonlar yig‘indisini hisoblash algoritmi. Blok sxemalarining takrorlanuvchi qismlarini, quyidagi parametrli takrorlash strukturasi ko‘rinishida ham ifodalash mumkin.Parametrli takrorlash operatorining umumiy ko‘rinishiParametrli takrorlash operatoriga misol sifatida berilgan x=1,2,3,.....10 larda funksiyasining qiymatlarini hisoblash blok sxemasini qarash mumkin.
Ichma-ich joylashgan siklik algoritmlar .Ba’zan, takrorlanuvchi algoritmlar bir nechta parametrlarga bog‘liq bo‘ladi. Odatda bunday algoritmlarni ichma-ich joylashgan algortmlar deb ataladi.
Misol sifati berilgan nxm o‘lchovli aij –matritsa elementlarining yig‘indisini hisoblash masalasini qaraylik.
Bu yig‘indi hisoblash uchun, i ning har bir qiymatida j bo‘yicha ko‘paytmani hisoblab, avval yig‘indi ustiga ketma-ket qo‘shib borish kerak bo‘ladi. Bu jarayon quyidagi blok–sxemada aks ettirilgan. Bu yig‘indi hisoblash uchun, i ning har bir qiymatida j bo‘yicha ko‘paytmani hisoblab, avval yig‘indi ustiga ketma-ket qo‘shib borish kerak bo‘ladi. Bu jarayon quyidagi blok–sxemada aks ettirilgan. Bu yerda i-tashqi sikl - yig‘indi uchun, j-esa ichki sikl-ko‘paytmani hosil qilish uchun foydalanilgan.
Yuqorida qayd qilganimizdek, qo‘yilgan biror masalani EHMda yechish uchun, avval uning matematik modelini, keyin algoritmini va programmasini tuzish kerak bo‘ladi. Bu uchlikda algoritm bloki muhim ahamiyatga ega. Endi algoritm tushunchasining ta’rifi va xossalarini bayon qilamiz.
Algoritm bu oldimizga qo‘yilgan masalani yechish zarur bo‘lgan amallar ketma-ketligidir.
Algoritm so‘zi va tushunchasi IX asrda yashab ijod etgan buyur alloma Muhammad al-Xorazmiy nomi bilan uzviy bog‘liq. Algoritm so‘zi Al-Xorazmiy nomini Yevropa olimlari tomonidan buzib talaffuz qilinishidan yuzaga kelgan. Al-Xorazmiy birinchi bo‘lib o‘nlik sanoq sistemasining tamoyillarini va undagi to‘rtta amallarni bajarish qoidalarini asoslab bergan.
Algoritmning asosiy xossalari.Algoritmning 5-ta asosiy xossasi bor:
Diskretlilik (Cheklilik). Bu xossaning mazmuni algoritmlarni doimo chekli qadamlardan iborat qilib bo‘laklash imkoniyati mavjudligida. Ya’ni uni chekli sondagi oddiy ko‘rsatmalar ketma-ketligi shaklida ifodalash mumkin. Agar kuzatilayotgan jarayonni chekli qadamlardan iborat qilib qo‘llay olmasak, uni algoritm deb bo‘lmaydi.
Tushunarlilik. Biz kundalik hayotimizda berilgan algoritmlar bilan ishlayotgan elektron soatlar, mashinalar, dastgohlar, kompyuterlar, turli avtomatik va mexanik qurilmalarni kuzatamiz.
Ijrochiga tavsiya etilayotgan ko‘rsatmalar, uning uchun tushinarli mazmunda bo‘lishi shart, aks holda ijrochi oddiygina amalni ham bajara olmaydi. Undan tashqari, ijrochi har qanday amalni bajara olmasligi ham mumkin.
Har bir ijrochining bajarishi mumkin bo‘lgan ko‘rsatmalar yoki buyruqlar majmuasi mavjud, u ijrochining ko‘rsatmalar tizimi (sistemasi) deyiladi. Demak, ijrochi uchun berilayotgan har bir ko‘rsatma ijrochining ko‘rsatmalar tizimiga mansub bo‘lishi lozim.
Ko‘rsatmalarni ijrochining ko‘rsatmalar tizimiga tegishli bo‘ladigan qilib ifodalay bilishimiz muhim ahamiyatga ega. Masalan, quyi sinfning a’lochi o‘quvchisi "son kvadratga oshirilsin" degan ko‘rsatmani tushinmasligi natijasida bajara olmaydi, lekin "son o‘zini o‘ziga ko‘paytirilsin" shaklidagi ko‘rsatmani bemalol bajaradi, chunki u ko‘rsatma mazmunidan ko‘paytirish amalini bajarish kerakligini anglaydi.
Aniqlik. Ijrochiga berilayotgan ko‘rsatmalar aniq mazmunda bo‘lishi zarur. Chunki ko‘rsatmadagi noaniqliklar mo‘ljaldagi maqsadga erishishga olib kelmaydi. Odam uchun tushinarli bo‘lgan "3-4 marta silkitilsin", "5-10 daqiqa qizdirilsin", "1-2 qoshiq solinsin", "tenglamalardan biri yechilsin" kabi noaniq ko‘rsatmalar robot yoki kompyuterni qiyin ahvolga solib qo‘yadi.
Bundan tashqari, ko‘rsatmalarning qaysi ketma-ketlikda bajarilishi ham muhim ahamiyatga ega. Demak, ko‘rsatmalar aniq berilishi va faqat algoritmda ko‘rsatilgan tartibda bajarilishi shart ekan.
Ommaviylik. Har bir algoritm mazmuniga ko‘ra bir turdagi masalalarning barchasi uchun ham o‘rinli bo‘lishi kerak. YA’ni masaladagi boshlang‘ich ma’lumotlar qanday bo‘lishidan qat’iy nazar algorim shu xildagi har qanday masalani yechishga yaroqli bo‘lishi kerak. Masalan, ikki oddiy kasrning umumiy mahrajini topish algoritmi, kasrlarni turlicha o‘zgartirib bersangiz ham ularning umumiy mahrajlarini aniqlab beraveradi. Yoki uchburchakning yuzini topish algoritmi, uchburchakning qanday bo‘lishidan qat’iy nazar, uning yuzini hisoblab beraveradi.
Natijaviylik. Har bir algoritm chekli sondagi qadamlardan so‘ng albatta natija berishi shart. Bajariladigan amallar ko‘p bo‘lsa ham baribir natijaga olib kelishi kerak. Chekli qadamdan so‘ng qo‘yilgan masala yechimga ega emasligini aniqlash ham natija hisoblanadi. Agar ko‘rilayotgan jarayon cheksiz davom etib natija bermasa, uni algoritm deb atay olmaymiz.
Algoritmning tasvirlash usullari .Yuqorida ko‘rilgan misollarda odatda biz masalani yechish algoritmini so‘zlar va matematik formulalar orqali ifodaladik. Lekin algoritm boshqa ko‘rinishlarda ham berilishi mumkin. Biz endi algoritmlarning eng ko‘p uchraydigan turlari bilan tanishamiz.
1.Algoritmning so‘zlar orqali ifodalanishi. Bu usulda ijrochi uchun beriladigan har bir ko‘rsatma jumlalar, so‘zlar orqali buyruq shaklida beriladi.
2. Algoritmning formulalar bilan berilish usulidan matematika, fizika, kimyo kabi aniq fanlardagi formulalarni o‘rganishda foydalaniladi. Bu usulni ba’zan analitik ifodalash deyiladi.
3. Algoritmlarning grafik shaklida tasvirlanishida algoritmlar maxsus geometrik figuralar yordamida tasvirlanadi va bu grafik ko‘rinishi blok-sxema deyiladi.
4. Algoritmning jadval ko‘rinishda berilishi. Algoritmning bu tarzda tasvirlanishdan ham ko‘p foydalanamiz. Masalan, maktabda qo‘llanib kelinayotgan to‘rt xonali matematik jadvallar yoki turli xil lotereyalar jadvallari. Funksiyalarning grafiklarini chizishda ham algoritmlarning qiymatlari jadvali ko‘rinishlaridan foydalanamiz. Bu kabi jadvallardan foydalanish algoritmlari sodda bo‘lgan tufayli ularni o‘zlashtirib olish oson.
Yuqorida ko‘rilgan algoritmlarning tasvirlash usullarining asosiy maqsadi, qo‘yilgan masalani yechish uchun zarur bo‘lgan amallar ketma-ketligining eng qulay holatinni aniqlash va shu bilan odam tomonidan programma yozishni yanada osonlashtirishdan iborat. Aslida programma ham algoritmning boshqa bir ko‘rinishi bo‘lib, u insonning kompyuter bilan muloqotini qulayroq amalga oshirish uchun mo‘ljallangan.
Blok-sxemalar bilan ishlashni yaxshilab o‘zlashtirib olish zarur, chunki bu usul algoritmlarni ifodalashning qulay vositalaridan biri bo‘lib programma tuzishni osonlashtiradi, programmalash qobiliyatini mustahkamlaydi. Algoritmik tillarda blok - sxemaning asosiy strukturalariga maxsus operatorlar mos keladi.
Shuni aytish kerakni, blok-sxemalardagi yozuvlar odatdagi yozuvlardan katta farq qilmaydi.
Misol sifatida ax2+bx+c=0 kvadrat tenglamani yechish algoritmining blok-sxemasi quyida keltirilgan.
Chiziqli algoritmlar.Har qanday murakkab algoritmni ham uchta asosiy struktura yordamida tasvirlash mumkin. Bular ketma-ketlik, ayri va takrorlash strukturalaridir. Bu strukturalar asosida chiziqli, tarmoqlanuvchi va takrorlanuvchi hisoblash jarayonlarining algoritmlarini tuzish mumkin. Umuman olganda, algoritmlarni shartli ravishda quyidagi turlarga ajratish mumkin:
chiziqli algoritmlar;
tarmoqlanuvchi algoritmlar;
takrorlanuvchi yoki siklik algoritmlar;
ichma-ich joylashgan siklik algoritmlar;
rekurrent algoritmlar;
takrorlanishlar soni oldindan no’malum algoritmlar;
ketma-ket yaqinlashuvchi algoritmlar.
Faqat ketma-ket bajariladigan amallardan tashkil topgan algoritmlarga-chiziqli algoritmlar deyiladi. Bunday algoritmni ifodalash uchun ketma-ketlik strukturasi ishlatiladi. Strukturada bajariladigan amal mos keluvchi shakl bilan ko‘rsatiladi. Chiziqli algoritmlar blok-sxemasining umumiy strukturasini quyidagi ko‘rinishda ifodalash mumkin:
Yuqorida keltirilgan algoritm va blok sxemadan ko‘rinib turibdiki amallar ketma-ketligining ma’lum qismi parametr i ga nisbatan N marta takrorlanayapti.
Yuqorida ko‘rilgan yig‘indi blok sxemalaridagi takrorlanuvchi qismlariga (aylana ichiga olingan) quyidagi sharti keyin berilgan siklik struktura mos kelishini ko‘rish mumkin. Yuqoridagi blok sxemalarda shartni oldin tekshiriladigan holatda chizish mumkin edi. Masalan, yig‘indining algoritmini qaraylik. Bu blok sxemaning takrorlanuvchi qismiga quyidagi, sharti oldin berilgan siklik strukturaning mos kelishini ko‘rish mumkin.
1-misol:
Hilbertning 10-muammosi.
D. Gilbert 1901 yilda diofant tenglamalarini yechishda quyidagi masalani ilgari suradi:
Ixtiyoriy Diofant tenglamasi uchun qandaydir butun son yechimini aniqlaydigan algoritmni toping.
F(x, y, …)=0
Bu noma'lumlar uchun butun ko'rsatkichli va butun son koeffitsientli polinom
anxn + an-1xn-1 +… + a2x2 + a1x + a0 = 0
Yuqoridagi tenglama uchun ma'lum bir yechim mavjud bo'lib, u har bir butun son ildizidan iborat xi bo'luvchi hisoblanadi a0 ... Qayerda a0 asosiy omillarga ajrating va har bir omilni ildizga muvofiqligini tekshiring.
1970 yilda leningradlik matematik Yu.Matiyasevich Diofant tenglamasini umumiy shaklda yechishning algoritmik imkonsizligini matematik tarzda isbotladi.
2-misol:
Ferma teoremasi:
Bunday butun sonlar mavjud emas a, b, s, n (n>2) buning uchun tenglik
a + bn = cn
Bu teorema ko'p qiymatlar uchun isbotlangan n va maxsus holatlar uchun tekshiriladi, lekin teoremaning umumiy isboti hali yaratilmagan.
3-misol:
Goldbax muammosi.
X. Xolbax 1742 yilda Eylerga yo‘llagan maktubida muammoni shunday shakllantirgan:
Har bir butun sonni isbotlang N³ 6 uchta tub sonning yig'indisi sifatida ifodalanishi mumkin
N= a+ b+ c
Bu shuni anglatadiki, siz har qanday butun songa ruxsat beradigan algoritmni topishingiz kerak N³ 6 kamida bitta parchalanishni uchta oddiy atamaga toping.
Eyler bu muammoni tez-tez hal qilishni taklif qildi: hatto uchun N bu muammo echilishi mumkin va ikkita oddiy atamaga parchalanishga teng.
I. Vinogradov 1937 yilda buni g'alati ekanligini isbotladi N uchta oddiy atamani topish mumkin, lekin juft sonlar uchun yechim hali topilmagan.
O (1) - Dasturdagi amallarning aksariyati faqat bir marta yoki bir necha marta bajariladi. Doimiy murakkablik algoritmlari. Ma'lumotlar hajmidan qat'i nazar, har doim bir xil vaqtni talab qiladigan har qanday algoritm doimiy murakkablik.
O (N) - Dasturning ishlash vaqti chiziqli odatda kirishning har bir elementi faqat chiziqli marta qayta ishlanishi kerak bo'lganda.
O (N 2), O (N 3), O (N a) - Polinom murakkabligi.
O (N 2) -kvadrat murakkablik, O (N 3) - kubik murakkablik
O (Log (N)) - Dastur qachon ishlaydi logarifmik, dastur N ortishi bilan ancha sekinroq ishlay boshlaydi. Bunday ish vaqtlari odatda katta masalani kichiklarga ajratadigan va ularni alohida yechiydigan dasturlarda uchraydi.
O (N * log (N)) - Bunday ish vaqti o'sha algoritmlarga ega katta muammoni kichikga bo'lish, va keyin ularni hal qilib, ularning echimlarini birlashtiring.
O (2 N) = Eksponensial murakkablik. Bunday algoritmlar ko'pincha qo'pol kuch deb ataladigan yondashuvdan kelib chiqadi.
Dasturchi algoritmlarni tahlil qilish va ularning murakkabligini aniqlay olishi kerak. Algoritmning vaqt murakkabligini uning boshqaruv tuzilmalarini tahlil qilish asosida hisoblash mumkin.
O (H) = O (1) + O (1) + O (1) = O (1);
O (I) = O (N) * (O (F) + O (J)) = O (N) * O (shart dominantlari) = O (N);
O (G) = O (N) * (O (C) + O (I) + O (K)) = O (N) * (O (1) + O (N) + O (1)) = O (N 2);
O (E) = O (N) * (O (B) + O (G) + O (L)) = O (N) * O (N 2) = O (N 3);
O (D) = O (A) + O (E) = O (1) + O (N 3) = O (N 3)
Bu algoritmning murakkabligi O (N 3).
Qoida tariqasida, dasturning ishlash vaqtining taxminan 90% takrorlashni talab qiladi va faqat 10% to'g'ridan-to'g'ri hisoblanadi. Dasturlarning murakkabligini tahlil qilish shuni ko'rsatadiki, qaysi qismlar ushbu 90% ga to'g'ri keladi - bular eng katta chuqurlikdagi tsikllardir. Takrorlashlar o'rnatilgan halqalar yoki ichki rekursiya sifatida tashkil etilishi mumkin.
Ushbu ma'lumotlardan dasturchi samaraliroq dastur yaratish uchun quyidagi tarzda foydalanishi mumkin. Avvalo, takrorlashning chuqurligini kamaytirishga harakat qilishingiz mumkin. Keyin eng chuqur halqalardagi bayonotlar sonini kamaytirish haqida o'ylashingiz kerak. Agar bajarilish vaqtining 90% ichki halqalarni bajarishda bo'lsa, u holda bu kichik bo'limlarning 30% ga qisqarishi butun dasturni bajarish vaqtining 90% * 30% = 27% qisqarishiga olib keladi.
Bu eng oddiy misol.
Matematikaning alohida bo'limi algoritmlarning samaradorligini tahlil qilish bilan shug'ullanadi va eng maqbul funktsiyani topish unchalik oson emas.
Keling, baho beramiz massivdagi ikkilik qidiruv algoritmi - dixotomiya.
Algoritmning mohiyati: biz massivning o'rtasiga o'tamiz va kalitning o'rta element qiymatiga mos kelishini qidiramiz. Agar moslikni topa olmasak, biz kalitning nisbiy hajmi va median qiymatini ko'rib chiqamiz va keyin ro'yxatning pastki yoki yuqori yarmiga o'tamiz. Bu yarmida biz yana o'rtani qidiramiz va yana kalit bilan taqqoslaymiz. Agar u ishlamasa, joriy intervalni yana yarmiga bo'ling.
funktsiyani qidirish (past, yuqori, kalit: integer): butun;
var
o'rta, ma'lumotlar: butun son;
boshlash
past bo'lganda<=high do
boshlash
o'rta: = (past + yuqori) div 2;
ma'lumotlar: = a;
agar kalit = ma'lumotlar bo'lsa
qidiruv: = o'rta
boshqa
kalit bo'lsa< data then
yuqori: = o'rta-1
boshqa
past: = o'rta + 1;
oxiri;
qidiruv: = - 1;
oxiri;
Loopning birinchi iteratsiyasi butun ro'yxat bilan bog'liq. Har bir keyingi iteratsiya pastki ro'yxat hajmini yarmiga qisqartiradi. Shunday qilib, algoritm uchun ro'yxatning o'lchamlari
n n / 2 1 n / 2 2 n / 2 3 n / 2 4 ... n / 2 m
Oxirida shunday m butun soni bo'ladi
n / 2 m<2 или n<2 m+1
Chunki m n / 2 m bo'lgan birinchi butun sondir<2, то должно быть верно
n / 2 m-1> = 2 yoki 2 m =
Bundan kelib chiqadi
2 m = Tengsizlikning har bir qismining logarifmini olamiz va olamiz
m = m qiymati = bo'lgan eng katta butun sondir<х.
Shunday qilib, O (log 2 n).Odatda hal qilinayotgan muammoning tabiiy “o‘lchami” (odatda u ishlov beradigan ma’lumotlar miqdori) bo‘ladi, biz uni N deb ataymiz. Oxir oqibat, biz N o‘lchamdagi ma’lumotlarni qayta ishlash uchun dastur uchun zarur bo‘lgan vaqt uchun ifodani olishni istaymiz. funksiyasi N. Odatda bizni o'rtacha holat qiziqtirmaydi - "odatiy" kirishlar bo'yicha dasturning kutilayotgan ish vaqti, eng yomoni esa eng yomon kiritish bo'yicha dasturning kutilayotgan ish vaqti.
Ba'zi algoritmlar o'rtacha va eng yomon holatlar uchun aniq matematik formulalar ma'lum bo'lgan ma'noda yaxshi o'rganilgan. Bunday formulalar matematik xarakteristikalar bo'yicha ishlash vaqtini topish uchun dasturlarni sinchkovlik bilan o'rganish va keyin ularning matematik tahlilini o'tkazish orqali ishlab chiqiladi.
Ushbu turdagi tahlil uchun bir nechta muhim sabablar mavjud:
1. Yuqori darajadagi tilda yozilgan dasturlar mashina kodlariga tarjima qilinadi va u yoki bu operatorni bajarish uchun qancha vaqt ketishini tushunish qiyin bo'lishi mumkin.
2. Ko'pgina dasturlar kiritilgan ma'lumotlarga juda sezgir va ularning ishlashi ularga juda bog'liq bo'lishi mumkin. O'rtacha holat dastur qo'llaniladigan ma'lumotlar bilan bog'liq bo'lmagan matematik fantastika bo'lib chiqishi mumkin va eng yomon holat bo'lishi mumkin emas.
Saralashda eng yaxshi, o'rtacha va eng yomon holatlar katta rol o'ynaydi.
Saralash hisobi
O-murakkablik tahlili ko'plab amaliy dasturlarda keng tarqaldi. Shunga qaramay, uning cheklovlarini aniq tushunish kerak.
TO yondashuvning asosiy kamchiliklari quyidagilarni o'z ichiga oladi:
1) murakkab algoritmlar uchun O-baholarini olish, qoida tariqasida, juda ko'p vaqt talab qiladi yoki deyarli imkonsizdir;
2) ko'pincha "o'rtacha" murakkablikni aniqlash qiyin,
3) O-baholari algoritmlar orasidagi nozik farqlarni aks ettirish uchun juda qo'pol,
4) O-tahlil kichik hajmdagi ma'lumotlarni qayta ishlashda algoritmlarning harakatini tahlil qilish uchun juda kam ma'lumot beradi (yoki umuman bermaydi).
O-notatsiyasida murakkablikni aniqlash ahamiyatsiz emas. Xususan, ikkilik qidiruvning samaradorligi pastadirlarni joylashtirish chuqurligi bilan emas, balki har bir keyingi urinishni tanlash usuli bilan belgilanadi.
Yana bir qiyin qism - "o'rtacha holat" ni aniqlash. Algoritmning ishlash shartlarini bashorat qilishning iloji yo'qligi sababli buni qilish odatda juda qiyin. Ba'zan algoritm katta, murakkab dasturning bir qismi sifatida ishlatiladi. Ba'zan apparat va/yoki operatsion tizimning samaradorligi yoki kompilyatorning ba'zi komponentlari algoritmning murakkabligiga sezilarli ta'sir qiladi. Ko'pincha, bir xil algoritm turli xil ilovalarda ishlatilishi mumkin.
Algoritmning vaqt murakkabligini "o'rtacha" tahlil qilish bilan bog'liq qiyinchiliklar tufayli ko'pincha eng yomon va eng yaxshi holatlar uchun taxminlar bilan kifoyalanish kerak. Ushbu hisob-kitoblar asosan "o'rtacha" qiyinchilikning pastki va yuqori chegaralarini belgilaydi. Aslida, agar algoritmning murakkabligini "o'rtacha" tahlil qilishning iloji bo'lmasa, Merfi qonunlaridan biriga amal qilish kerak, unga ko'ra eng yomon holat uchun olingan baho "o'rtacha" murakkablikning yaxshi yaqinlashuvi bo'lib xizmat qilishi mumkin. ".
Ehtimol, O-funksiyalarining asosiy kamchiliklari ularning juda qo'polligidir. Agar A algoritmi qandaydir vazifani 0,001 * N s da bajarsa, uni B algoritmidan foydalangan holda hal qilish uchun 1000 * N s kerak bo'lsa, u holda B A dan million marta tezroq bo'ladi. Shunga qaramay, A va B bir xil vaqt murakkabligi O ga ega. (N).
Ushbu ma'ruzaning ko'p qismi algoritmlarning vaqt murakkabligini tahlil qilishga bag'ishlangan. Murakkablikning boshqa shakllari ham borki, ularni unutmaslik kerak: fazoviy va intellektual murakkablik.
Fazoviy murakkablik, dasturni bajarish uchun zarur bo'lgan xotira miqdori haqida avval aytib o'tilgan edi.
Algoritmning intellektual murakkabligini tahlil qilishda algoritmlarning tushunarliligi va ularni ishlab chiqishning murakkabligi tekshiriladi.
Murakkablikning barcha uchta shakli odatda o'zaro bog'liqdir. Odatda, yaxshi vaqtinchalik murakkablik hisobiga ega algoritmni ishlab chiqishda uning fazoviy va/yoki intellektual murakkabligidan voz kechish kerak. Misol uchun, tez tartiblash algoritmi namunaviy tartiblash algoritmidan sezilarli darajada tezroq. Saralash tezligini oshirish uchun to'lov saralash uchun zarur bo'lgan ko'proq xotirada ifodalanadi. Tez tartiblash uchun qo'shimcha xotiraga bo'lgan ehtiyoj bir nechta rekursiv qo'ng'iroqlar bilan bog'liq.
Quicksort, shuningdek, kiritish tartibidan ko'ra aqlliroq murakkabroq. Agar siz yuzlab odamlardan ob'ektlar ketma-ketligini saralashni so'rasangiz, ularning aksariyati namunaviy tartiblash algoritmidan foydalanadi. Ulardan birortasi ham tezkor saralashdan foydalanishi dargumon. Tez tartiblashning ko'proq intellektual va fazoviy murakkabligining sabablari aniq: algoritm rekursiv, uni tasvirlash ancha qiyin, algoritm oddiyroq tartiblash algoritmlariga qaraganda uzunroq (dastur matnini anglatadi).
Ko'pincha bir xil muammoni hal qilish uchun bir nechta algoritmlar ishlab chiqilishi mumkin. Shu munosabat bilan savol tug'iladi: algoritmlarning qaysi biri "yaxshiroq"?
Ko'pgina hollarda, "yaxshiroq", aftidan, xuddi shu kiritilgan ma'lumotlardan foydalangan holda, kamroq hisoblash resurslarini (xotira va vaqt) sarflaydigan muammoni hal qilishga keladigan algoritmdir. Bu, albatta, bo'sh fikr. Aniqroq fikr yuritish uchun biz bir nechta tushunchalarni kiritamiz.
Algoritmni hisoblash jarayoni - bu ba'zi kiritilgan ma'lumotlar uchun algoritmning bajarilishidan o'tgan bosqichlar ketma-ketligi.
Algoritmning o'zi va ushbu algoritm tomonidan yaratilgan hisoblash jarayoni o'rtasidagi farqni tushunish muhimdir. Birinchisi faqat tavsifi ikkinchi.
Algoritmning vaqt murakkabligi - ba'zi kiritilgan ma'lumotlar uchun algoritmning hisoblash jarayonini yakunlash uchun zarur bo'lgan vaqt \ (T \).
Amalga oshirish muddati aniq ijrochiga bog'liqligi aniq. Aytaylik, elektron kalkulyator va superkompyuter bir xil algoritmni turli vaqtlarda ishlatishi mumkin.
Biroq, \ (T \) vaqtni elementar harakatlar soni \ (k \) va elementar harakatning o'rtacha bajarilish vaqti \ (t \) bilan ifodalash mumkin:
Bundan tashqari, \ (k \) xususiyatdir eng algoritm, va \ (t \) - ijrochining xossasi.
Berilgan ijrochi uchun \ (t \) doimiy deb hisoblanishi mumkinligi sababli, odatda algoritmlarning murakkabligi doimiy koeffitsientgacha baholanadi. Boshqacha qilib aytganda, algoritmning murakkabligi taxmin qilinadi o'sish tartibi.
O'sish tartibi musbat aniq funksiya \ (g (x) \) o'sish tartibiga ega \ (f (x) \) (yozma \ (g (x) = \ mathcal (O) (f (x)) \)) agar \ (\ mavjud c> 0: \: \ forall x> x_0, \, g (x) \ leq c f (x) \).
Kirish ma'lumotlariga qarab, algoritm turli vaqtlarda ishlashi mumkin. Odatda baholanadi o'rtacha murakkablik va murakkablik eng yomoni... ga qaramlik ham mavjud miqdori ma'lumotlarni kiritish \ (n \). Odatda \ (n \) ning o'sish tartibi baholanadi.
Masalan, ma'lumotlarni o'qish va uni xotirada massiv sifatida saqlash murakkablikga ega bo'ladi \ (\ mathcal (O) (n) \) yoki chiziqli murakkablik, va matritsani ko'paytirish allaqachon kub\ (\ matematik (O) (n ^ 3) \).
Algoritmning vaqt murakkabligidan tashqari, u ham muhimdir fazoviy algoritmning murakkabligi.
Algoritmning fazoviy murakkabligi sondir qo'shimcha xotira \ (S \), algoritm ishlashi uchun talab qilinadi. Kirish ma'lumotlarini saqlash uchun zarur bo'lgan xotira \ (D \) \ (S \) tarkibiga kiritilmagan.
\ (S \) odatda aktuatorga ham bog'liq. Misol uchun, agar ikkita aktuator mos ravishda 4 va 8 baytli butun sonlarni qo'llab-quvvatlasa, u holda 8 baytli butun sonlar uchun algoritmning fazoviy murakkabligi 4 baytli butun sonlarga qaraganda ikki baravar katta bo'ladi. Shuning uchun fazoviy murakkablik bir xil o'sish tartibida baholanadi.
Koʻrsatkich koʻtarish
Ushbu algoritm qadimgi Hindistonda bizning eramizdan oldin tasvirlangan va haqiqiy sonning \ (n \) tabiiy kuchini \ (x \) hisoblash uchun ishlatiladi.
1. \ (n \) ni ikkilik tizimda yozing
2. Ushbu yozuvdagi 1 ning har birini bir juft KX harfi bilan, har bir 0 ni esa K harfi bilan almashtiring
3. Eng chapdagi KX juftligini kesib tashlang
4. Olingan satrni chapdan o'ngga o'qish, K harfi bilan uchrashish, natijani kvadratga tushirish va X harfini uchratish, natijani x ga ko'paytiring. Boshida natija x ga teng.
Bu algoritmda biz ko'paytirish amallari soni ikkilik ko'rinishdagi raqamlar soniga eng yaxshi \ (n \) va eng yomoni \ (2 (n-1) \) ga teng. Vaqt murakkabligi baribir.
Algoritmni samarali amalga oshirishda qo'shimcha xotira amalda talab qilinmaydi va u kiritilgan ma'lumotlarga bog'liq emas, shuning uchun fazoviy murakkablik \ (S (n) = \ matematik (O) (1) \) ga teng.
Shuni ta'kidlash kerakki, yanada samarali algoritmlar mavjud. Biroq, \ (\ mathcal (O) (n) \) ko'paytirish operatsiyalarini talab qiladigan "sodda" amalga oshirish bilan solishtirganda, bu algoritm nisbatan samarali.
Butun sonlarni ko‘paytirish
Ushbu ko'paytirish algoritmi ba'zan rus yoki dehqon deb ataladi, garchi u Qadimgi Misrda ham ma'lum bo'lgan.
Birinchi omil ketma-ket ikkiga ko'paytiriladi, ikkinchisi esa to'liq 2 ga bo'linadi. Natijalar ikkinchisi 1 bo'lguncha ikkita ustunga yoziladi.
Ko'paytirish natijasi birinchi ustundagi raqamlarning yig'indisi, ikkinchi ustundagi toq raqamlarning qarama-qarshiligi.
Butun sonlarni bo'lish va 2 ga ko'paytirishni siljish yo'li bilan bajarish mumkin bo'lganligi sababli, bu algoritm \ (2 \ log_2 n \) siljish amallarini beradi, bu erda \ (n \) ikkita sondan kichikroqdir. Eng yomon holatda, \ (\ log_2 n - 1 \) qo'shish operatsiyalari ham olinadi. Qanday bo'lmasin, vaqtning murakkabligi \ (T (n) = \ matematik (O) (\ log n) \).
Algoritmni samarali amalga oshirish uchun qo'shimcha xotira deyarli talab qilinmaydi va u kiritilgan ma'lumotlarga bog'liq emas, shuning uchun \ (S (n) = \ mathcal (O) (1) \)
Yana shuni ta'kidlash kerakki, yanada samarali algoritmlar mavjud. Biroq, \ (\ mathcal (O) (n) \) qo'shish operatsiyalarini talab qiladigan "sodda" amalga oshirish bilan solishtirganda, bu algoritm nisbatan samaralidir.
Misol
23 ni 43 ga ko'paytiring.
Ikkinchi omil sifatida 23 ni olaylik.
43 23 g'alati
86 11 g'alati
172 5 g'alati
344 2
688 1 g'alati
Natija \ (43 + 86 + 172 + 688 = 989 \)
Bizda 10 ta smenali operatsiya va 4 ta qo'shimcha operatsiya mavjud. Malumot uchun, \ (\ log_2 (23) \ taxminan 4,52 \).
Algoritmning murakkabligini aniqlash
Asimptotik tahlilda olingan murakkablik funksiyasining bahosi algoritmning murakkabligi deyiladi.
Shuni yodda tutish kerakki, algoritmning murakkabligi bo'yicha bir nechta taxminlar mavjud.
Murakkablik funktsiyasining asimptotik xatti-harakati operatsion murakkablikdir. Unga qo'shimcha ravishda siz quyidagi qiyinchiliklar turlarini belgilashingiz mumkin.
Vaqtinchalik murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmning ishlash vaqtining asimptotik bahosi P. Shubhasiz, hisoblash protseduralarini parallellashtirish mavjud bo'lmaganda, algoritmning ishlash vaqti bajarilgan operatsiyalar soni bilan yagona aniqlanadi. Operatsiyalarning davomiyligini ifodalovchi doimiy koeffitsientlar vaqt murakkabligi tartibiga ta'sir qilmaydi, shuning uchun operatsion va vaqt murakkabligi uchun formulalar ko'pincha bir-biriga to'g'ri keladi.
Kapasitiv murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmni bajarishda bir vaqtning o'zida mavjud bo'lgan skalerlar sonining asimptotik bahosi P.
Strukturaviy murakkablik - algoritmdagi boshqaruv tuzilmalari sonining xarakteristikasi va ularning interpozitsiyasining o'ziga xosligi.
Kognitiv murakkablik - amaliy sohalardagi mutaxassislar tomonidan tushunish uchun algoritm mavjudligining xarakteristikasi.
Amalda, qayta Ba'zi hisob-kitoblarda M ning murakkabligini matematik kutishning f (n) bahosi katta qiziqish uyg'otadi, chunki aksariyat hollarda f (n) tasodifiy funktsiyadir. Biroq, tasodifiy f (i) bilan algoritmlarni eksperimental o'rganish jarayonida qo'shimcha muammo tug'iladi - M ni ishonchli baholash uchun testlar sonini tanlash. Taklif etilayotgan yechim / (i) ni taxmin qilish uchun beta taqsimotidan foydalanishga asoslangan. Bu juda konstruktiv va ko'p qirrali texnika. Biroq, zamonaviy sharoitda, kompyuterning unumdorligi etarlicha yuqori bo'lsa, ko'p hollarda qiymatlarning joriy o'zgaruvchanligini nazorat qilish asosida testlar hajmini tanlashning oddiyroq usulini qo'llash mumkin. f (n) - qiymatlar baholarning o'zgaruvchanligi belgilangan xatolikdan kam bo'lgunga qadar baholanadi.
Algoritmning operatsion murakkabligini baholash
Algoritmning murakkabligini uning boshqaruv tuzilmalarini tahlil qilish asosida aniqlash mumkin. Loopsiz va rekursiv chaqiruvlarsiz algoritmlar doimiy murakkablikka ega. Shuning uchun algoritmning murakkabligini aniqlash asosan tsikllar va rekursiv chaqiruvlarni tahlil qilishga qisqartiriladi.
O'chirish algoritmini ko'rib chiqing Kimga o'lcham massividan th element P dan harakatlanuvchi massiv elementlaridan iborat (k + 1) dan P-massiv boshiga qaytish va elementlar sonini kamaytirish P birlik uchun. Massivni qayta ishlash siklining murakkabligi Oh (p-k) pastadir tanasi (harakat qilish operatsiyasi) bajarilganligi sababli Kompyuter marta, va pastadir tanasining murakkabligi 0 (1), ya'ni. doimiydir.
Ko'rib chiqilayotgan misolda murakkablik asimptotik 0 (") bilan tavsiflanadi, chunki bu algoritmda bajariladigan operatsiyalar soni ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas. Murakkablik funktsiyasi deterministik bo'lib, asimptotikaning barcha turlari bir-biriga to'g'ri keladi: f (n) = Q (n-k), f (n) = 0 (n-k) va f (n) = Q (n-dan). Bu fakt © () belgisi bilan tasdiqlanadi. 0 (*) va/yoki 2 (*) dan faqat ushbu asimptotiklar boshqacha bo'lsa foydalanish kerak.
Loop turi (for, while, takrorlash) murakkablikka ta'sir qilmaydi. Agar bir sikl boshqasiga o'rnatilgan bo'lsa va ikkala tsikl ham bir xil o'zgaruvchining o'lchamiga bog'liq bo'lsa, unda butun qurilish kvadratik murakkablik bilan tavsiflanadi. Takroriy uyalar qiyinchilikni oshiradigan asosiy omil hisoblanadi. Misol tariqasida, biz o'lchamdagi massiv uchun taniqli qidirish va saralash algoritmlarining murakkabligini keltiramiz. P:
• ketma-ket qidiruvda taqqoslash operatsiyalari soni: 0 (i);
• Ikkilik qidiruvda taqqoslash operatsiyalari soni: 0 (log 2 P);
• oddiy almashuv usulida taqqoslash operatsiyalari soni (qabariqli tartiblash): 0 (i 2);
• pufakchali tartibdagi almashtirish operatsiyalari soni: 0 (n 2);
E'tibor bering, oddiy almashish usulida taqqoslash operatsiyalari soni asimptotikaga ega 0 (n 2) va almashtirish operatsiyalari soni ikki xil asimptotikaga ega 0 (n 2) va? 2 (0), chunki taqqoslashlar soni saralangan ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas, almashtirishlar soni esa ushbu o'ziga xoslik bilan aniq belgilanadi. O'zgartirishlar umuman amalga oshirilmasligi mumkin - agar ma'lumotlar qatori dastlab to'g'ri tartiblangan bo'lsa yoki almashtirishlar soni maksimal bo'lishi mumkin - taxminan P 2, - agar tartiblangan massiv dastlab teskari yo'nalishda tartiblangan bo'lsa.
Teorema :
Qoniqish muammosi NP-to'liq.
xi tanlash (to'g'ri, noto'g'ri)
agar E (x1, x2,…, xN) bo'lsa, muvaffaqiyat
boshqa muvaffaqiyatsizlik
P1 muammosini P2 ga aylantirishdan foydalanib, qoniqish muammosining cheklangan holati ham NP-to'liq ekanligini ko'rsatish mumkin.
K - amalga oshirish imkoniyati .
K-qoniqarliligi CNFga kiritilgan har qanday bandda ko'pi bilan K mantiqiy o'zgaruvchilar mavjudligini anglatadi.
Doimiy vaqt
Algoritmga algoritm deyiladi doimiy vaqt(vaqt sifatida qayd etilgan O (1)) qiymat bo'lsa T(n) kirish hajmiga bog'liq bo'lmagan qiymat bilan cheklangan. Masalan, massivda bitta elementni olish doimiy vaqtni oladi, chunki uni topish uchun bitta buyruq bajariladi. Biroq, tartiblanmagan massivda minimal qiymatni topish doimiy vaqtdagi operatsiya emas, chunki biz massivning har bir elementini skanerlashimiz kerak. Shunday qilib, bu operatsiya chiziqli vaqtni oladi, O (n). Agar elementlarning soni oldindan ma'lum bo'lsa va o'zgarmasa, bunday algoritmni doimiy vaqt algoritmi deb atash mumkin.
"Doimiy vaqt" nomiga qaramay, ish vaqti vazifa hajmidan mustaqil bo'lishi shart emas, lekin ish vaqtining yuqori chegarasi bo'lmasligi kerak. Masalan, "qiymatlarni almashish" vazifasi a va b, zarur bo'lsa, natijada biz olamiz a≤b", doimiy vaqt muammosi hisoblanadi, garchi algoritmning ishlash vaqti tengsizlikning mavjudligiga bog'liq bo'lishi mumkin. a ≤ b yoki yo'q. Biroq, ma'lum bir doimiylik mavjud t, ular uchun vazifani bajarish vaqti har doim oshmaydi t.
Quyida doimiy vaqtda ishlaydigan ba'zi kod misollari keltirilgan:
Int indeksi = 5; int element = ro'yxat; agar(shart to'g'ri) keyinboshqa doimiy ish vaqti bilan ba'zi operatsiyalarni bajarish uchun i = 1 uchun 100 uchun j = 1 uchun 200 doimiy ish vaqti bilan ba'zi operatsiyalarni bajaradi
Agar T(n) bu O ( ba'zi doimiy qiymat), bu ga teng T(n) O (1) dir.
Logarifmik vaqt
logarifmik vaqt, agar T(n) = O (log n) ... Kompyuterlar ikkilik tizimdan foydalanganligi sababli, logarifmning asosi sifatida 2 ishlatiladi (ya'ni log 2). n). Biroq, bilan bazani almashtirish logaritmalar log a n va jurnal b n faqat doimiy koeffitsient bilan farqlanadi, bu esa O-katta belgisida bekor qilinadi. Shunday qilib, O (log n) - logarifm asosidan qat'iy nazar, logarifmik vaqt algoritmlari uchun standart belgi.
Logarifmik vaqt algoritmlari odatda binar daraxt operatsiyalarida yoki ikkilik qidiruvdan foydalanganda topiladi.
O (log n) algoritmlari yuqori samarali hisoblanadi, chunki har bir elementning bajarilish vaqti elementlar sonining ko'payishi bilan kamayadi.
Bunday algoritmning juda oddiy misoli qatorni ikkiga bo'lish, ikkinchi yarmini yana yarmiga bo'lish va hokazo. Bu O (log n) vaqtni oladi (bu erda n - satr uzunligi, biz bu erda taxmin qilamiz console.log va str.substring doimiy vaqt talab qiladi). Bu shuni anglatadiki, nashrlar sonini ko'paytirish uchun chiziq uzunligi ikki barobarga oshirilishi kerak.
// Chiziqning o'ng yarmini rekursiv chop etish funksiyasi var o'ng = funktsiya (str) (var uzunligi = ko'cha uzunligi; // yordamchi funksiya var help = funktsiya (indeks) ( // Rekursiya: o'ng yarmini chop eting agar (indeks< length ) { // Belgilarni indeksdan satr oxirigacha chop etish konsol. log (str. substring (indeks, uzunlik)); // rekursiv chaqiruv: o'ng tomoni bilan yordamchi funksiyani chaqiring yordam (Math.ceil ((uzunlik + indeks) / 2)); )) yordam (0); )
Polilogarifmik vaqt
Algoritm ishga kirishishi aytiladi polilogarifmik vaqt, agar T(n) = O ((log n) k), ba'zilar uchun k... Masalan, matritsalarni ko‘paytirish tartibi masalasini polilogarifmik vaqtda yechish mumkin. parallel PAM mashinasi .
Sublinear vaqt
Algoritm ishga kirishishi aytiladi sublinear vaqt, agar T(n) = o ( n). Xususan, bu yuqorida sanab o'tilgan vaqt murakkabligi algoritmlarini, shuningdek boshqalarni o'z ichiga oladi, masalan, Grover qidiruvi murakkabligi O ( n ½).
To'g'ri bo'lsa-da, hali ham subchiziqli vaqtda ishlaydigan odatiy algoritmlar jarayonlarni parallellashtirishdan (masalan, matritsa determinantini hisoblash uchun NC 1 algoritmida), klassik bo'lmagan hisoblashlardan (Grover qidiruvida bo'lgani kabi) yoki kafolatlangan taxminga ega bo'lgan algoritmlardan foydalanadi. kirishning tuzilishi (logarifmik vaqtda ishlaydigan, ikkilik qidiruv algoritmlari va ko'plab daraxtlarni qayta ishlash algoritmlari). Biroq, satrning birinchi log (n) bitlari tomonidan aniqlangan holatda 1 bitga ega bo'lgan barcha satrlar to'plami kabi rasmiy konstruktsiyalar kirishning har bir bitiga bog'liq bo'lishi mumkin, ammo vaqt o'tishi bilan hali ham pastki chiziqli bo'lib qoladi.
Muddati sublinear ish vaqti algoritmi odatda, yuqoridagi misollardan farqli o'laroq, an'anaviy ketma-ket mashina modellarida ishlaydigan va kirish strukturasi haqida aprior bilimni talab qilmaydigan algoritmlar uchun ishlatiladi. Biroq, ular uchun ehtimollik usullaridan foydalanishga ruxsat beriladi va undan ham ko'proq, algoritmlar eng ahamiyatsiz muammolar uchun ehtimollik bo'lishi kerak.
Bunday algoritm kirish ma'lumotlarini to'liq o'qimasdan javob berishi kerakligi sababli, bu kirish oqimida ruxsat etilgan kirish usullariga juda bog'liq. Odatda bit string oqimi uchun b 1 ,...,b k, algoritm qiymatni so'rashi mumkin deb taxmin qilinadi b i har kim uchun i.
Sublinear vaqt algoritmlari, qoida tariqasida, ehtimollikdir va faqat taxminiy echimni beradi. Sublinear ish vaqti algoritmlari tadqiqot paytida tabiiy ravishda paydo bo'ladi mulkni tekshirish.
Lineer vaqt
chiziqli vaqt, yoki O ( n) agar uning murakkabligi O bo'lsa ( n). Norasmiy ravishda, bu etarli darajada katta kirish hajmi uchun ish vaqti kirish hajmi bilan chiziqli ravishda oshib borishini anglatadi. Masalan, ro'yxatning barcha elementlarini jamlaydigan protsedura ro'yxat uzunligiga proportsional vaqtni oladi. Ushbu tavsif to'liq aniq emas, chunki ish vaqti aniq proportsionallikdan sezilarli darajada farq qilishi mumkin, ayniqsa kichik qiymatlar uchun. n.
Chiziqli vaqt ko'pincha algoritmning kerakli atributi sifatida qaraladi. (deyarli) chiziqli ish vaqti yoki undan yuqori bo'lgan algoritmlarni yaratish uchun ko'plab tadqiqotlar o'tkazildi. Ushbu tadqiqotlar dasturiy ta'minot va apparat yondashuvlarini o'z ichiga oladi. Uskunani bajarish holatida, standart hisoblash modellarida matematik jihatdan hech qachon chiziqli bajarish vaqtiga erisha olmaydigan ba'zi algoritmlar chiziqli vaqtda ishlashi mumkin. Ushbu maqsadga erishish uchun parallellikdan foydalanadigan ba'zi apparat texnologiyalari mavjud. Masalan, assotsiativ xotira. Ushbu chiziqli vaqt tushunchasi Boyer-Mur algoritmi va Ukkonen algoritmi kabi qatorlarni taqqoslash algoritmlarida qo'llaniladi.
Algorithm Murakkabligi
Algoritmning murakkabligi (complexity) Space (joy) va Time (vaqt) miqdori asosida o’lchanadigan qiymat. Bunda Time dasturning ishlash jarayonida ketqizadigan vaqti; Space esa input, o’zgaruvchilar, output uchun kerak bo’ladigan joy miqdori. Bu ikki faktor algoritmni effektivligini aniqlaydi. Yaxshi algoritmlarda Space va Time kam miqdorda bo’ladi, bu esa usha algoritmda yozilgan kodning ishlash tezligini, performanceni oshiradi.
Ko’p hollarda katta proyektlarda millionlab qator ma’lumotlar ustida amallar bajarishga to’g’ri keladi. Shunda kichik masalalarda sezilmagan kodning performance muammosi, katta hajmdagi ma’lumotlarni qayta ishlashda yaqqol ko’rinadi. Performance muammosi kodning ishlash tezligiga ta’sir qiladi, ishlashda xotiradan ko’proq joy egallashiga olib keladi.
Asl maqsad tech giant korporatsiyalarga ishga kirish ekan, performance’ni birinchi o’ringa qo’yish, yozilgan kodni tahlil qilib, complexity’ni aniqlay olish kerak bo’ladi.
Yaqinda o’zimizda bo’lib o’tgan performance muammosi haqida:
Backendni optimizatsiya qilish jarayonida bir millionga yaqin foydalanuvchi ma’lumotlarini yig’ib, bazada bir jadvalga saqlash kerak bo’lib qoldi. Frameworkning tayyor funksiyalari yordamida yozilgan kod, ishni tugatish uchun 5 soatdan ko’p vaqt olishi ma’lum bo’ldi. Turgan gapki, shuncha foydalanuvchisi bor saytni 5 soat o’chirib qo’yolmaymiz. Keyin kodni optimizatsiya qilib, frameworkni ishlatmasdan yozib chiqqanimda 40 minutda import qiladigan bo’ldi.
Algoritmlarni tahlil qilishni yana Asymptotic analysis ham deyiladi. Bunda kiritilgan input kattaligiga qarab algoritmning ishlash vaqti hisoblanadi.
Asymptotic analysis ga misol sifatida tartiblangan array’dan berilgan X sonni topish uchun Linear Search va Binary Search algoritmlarini taqqoslaymiz.
Linear search siklda arrayning birinchi elementidan boshlab X ni topguncha array elementlarini bittalab tekshirib chiqadi. Array uzunligini N deb oladigan bo’lsak, X ni topish uchun minimal 1 maksimal, N solishtirishni amalga oshiradi.
Binary search array’ning o’rtasidagi element qiymatini – M ni oladi va uni X bilan solishtiradi:
X M ga teng bo’lsa, bingo! birinchi urinishdayoq kerakli element topildi.
Agar X M dan kichik bo’lsa, demak qidirishni arrayning birinchi yarmidan davom ettirish kerak.
Agar X M dan katta bo’lsa, demak qidirishni arrayning ikkinchi yarmidan davom ettiriladi.
Hudi shunday uslubda, avval qismning o’rtasi M topiladi, keyin X ni M bilan solishtirib boriladi.
Bunda minimal urinish 1, maksimal urinish log N marta bo’ladi. Ya’ni array uzunligi 10 ta bo’lsa binary searchda maksimum 3 ta urinishda X ni topish mumkin. Linear searchda esa maksimum 10ta urinish bo’lgan bo’lardi. Endi 100,000 elementi bor katta arrayni oladigan bo’lsak:
Linear searchda max 100,000 urinish
Binary searchda max 16 urinish!
Har bir urinishni shartli ravishda 1 sekund deb hisoblaganda, linear search 27,78 soatda ishni tugatadi. Binary search 16 sekundda. Demak, ikki algoritmni solishtirganda eng yomon holatda (worst case) binary search 6250 marta tez ishlaydi.
Kerakli tanlangan algoritm dasturning ishlash tezligini oshiradi. Katta loyihalarda bo’lsa mablag’ tejalishiga olib keladi.
Biz aytib o’tgan urinishlar sonini aniqlashda ko’pincha best case, average case va worst case hisoblanadi.
Linear searchda va binary search’da best case 1.
Best case’ning yana bir nomi lower bound.
Worst case’niki – upper bound.
Lower bound va upper bound grekcha Θ harfi bilan yoziladi.
Linear search va binary search algoritmlari Θ da yozilganda:
Best case:
– linear search – Θ(1)
– binary search – Θ(1)
Worst case:
– linear search – Θ(n)
– binary search – Θ(log n)
Ba’zi algoritmlarda lower bound va upper bound bir xil bo’ladi, bu degani algoritm input kattaligidan qat’iy nazar, bir xil amalni bajaradi. Bunga misol qilib MergeSort ni keltirish mumkin. MergeSort‘da upper va lower bound bir xil – Θ(n log n).
Foydalanilgan adabiyotlar
1. Mirzayev A. N., Abduraxmanova Yu. M. “Iqtisodiy matematik usullar va modellar” o’quv qo’llanma. Tafakkur nashriyoti. Toshkent-2015.
2. Исроилов M. Ҳисоблаш методлари. 2-кисм. “Iqtisod-moliya”, Tошкент, 2008, 320 б.
3. M. Raisov. Matematik programmalashtirish. Toshkent-2013.
4. N. R. Beknazarova, X. N. Jumayev. Matematik programmalashtirish va optimallashtirish usullari. Toshkent “Iqtisodiyot” - 2011
|
