Toshkent axborot texnologiyalari universiteti mustaqil ish mavzu: Algoritm murakkabligini statik va dinamik o'lchovlari. Vaqt va xotira hajmi bo'yicha qiyinchiliklar
Download 296.98 Kb.
|
Algoritmlarni loyihalash zarif jorayev 99
- Bu sahifa navigatsiya:
- Bajardi : ZARIF JO’RAYEV Tekshirdi
- Chiziqli logarifmik funktsiya
|
O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI MUSTAQIL ISH MAVZU: Algoritm murakkabligini statik va dinamik o'lchovlari. Vaqt va xotira hajmi bo'yicha qiyinchiliklar. Guruh:413-19 Bajardi: ZARIF JO’RAYEV Tekshirdi: Begimov O’ktam Algoritm murakkabligini statik va dinamik o'lchovlari. Vaqt va xotira hajmi bo'yicha qiyinchiliklar. Reja: Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar. Algoritmlarni eng yomon va o‘rtacha xolatlarda baholash Algoritm murakkabligini baholash. Xotira yoki vaqt. Murakiblikni baxolash Xulosa Foydalanilgan adabiyotlar Kirish
Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabligi funksiyalarining turlari.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.Liner 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.Kvazilinear vaqt.Algoritm kvazizikli vaqtda ishlaydi, deyiladi, agar T(n) = O ( n jurnal k n) ba'zi doimiy uchun k... Chiziqli-logarifmik vaqt bilan alohida holat k= 1. Zaif-O belgilaridan foydalanilganda, bu algoritmlar Õ ( n). Kvazilinear vaqt algoritmlari ham o ( n 1 + e) har qanday e> 0 uchun va har qanday polinomdan tezroq ishlaydi n.Yuqorida aytib o'tilgan chiziqli-logarifmik algoritmlarga qo'shimcha ravishda, kvaziziiqli vaqtda ishlaydigan algoritmlarga quyidagilar kiradi: O'z joyida birlashtirish tartibi, O ( n jurnal 2 n) Tez tartiblash, O ( n jurnal n), ehtimolli versiyada eng yomon holatda chiziqli-logarifmik bajarilish vaqti mavjud. Mumkin bo'lmagan versiyada o'rtacha qiyinchilikni o'lchash uchun chiziqli jurnalning ishlash vaqti mavjud. Uyumni tanlash, O ( n jurnal n), birlashma tartiblash, introsort, ikkilik daraxt tartibi, silliq tartiblash, solitaire turi, va hokazo. eng yomoni Tez Furye o'zgarishi, O ( n jurnal n) Monge matritsalarini hisoblash, O ( n jurnal n) Chiziqli logarifmik vaqt.Chiziqli-logarifmik - bu ko'rsatkichli kvazizikli vaqtning maxsus holati k= 1 logarifmik hadda.Chiziqli logarifmik funktsiya shaklning funktsiyasidir n jurnal n(masalan, mahsulot chiziqli va logarifmik atamalar). Algoritm ishlashi aytiladi chiziqli-logarifmik vaqt, agar T(n) = O ( n jurnal n) ... Shunday qilib, chiziqli-logarifmik element chiziqli haddan tezroq, lekin har qanday polinomga qaraganda sekinroq o'sadi. n 1 dan qat'iy yuqori darajaga ega.Ko'p hollarda ish vaqti n jurnal n oddiygina operatsiya natijasidir t (log n) n bir marta. Masalan, ikkilik daraxt bilan tartiblash har bir elementni n o‘lchamli massivga birma-bir kiritish orqali ikkilik daraxt hosil qiladi. Insert operatsiyasidan beri muvozanatli ikkilik qidiruv daraxti O ni oladi (log n), algoritmning umumiy bajarilish vaqti chiziqli-logarifmik bo'ladi.Taqqoslash bo'yicha saralash hech bo'lmaganda logdan beri eng yomon holatlardagi taqqoslashlarning chiziqli jurnalini talab qiladi ( n!) = Θ( n jurnal n) Stirling formulasi bo'yicha. Xuddi shu bajarilish vaqti ko'pincha takrorlanish tenglamasidan kelib chiqadi T(n) = 2 T(n/ 2) + O ( n). Qattiq va kuchsiz polinom vaqti.Ba'zi kontekstlarda, ayniqsa optimallashtirishda, algoritmlar bilan ajralib turadi qat'iy polinom vaqti va zaif polinom vaqti... Bu ikki tushuncha faqat butun sonlardan tashkil topgan kiritish uchun amal qiladi.Arifmetik hisoblash modelida qat'iy polinom vaqti aniqlanadi. Bu modelda operandlar uzunligidan qat’iy nazar, bajarilish birliklari sifatida asosiy arifmetik amallar (qo‘shish, ayirish, ko‘paytirish, bo‘lish va taqqoslash) olinadi. Algoritm qat'iy polinom vaqtida ishlaydi, agar arifmetik hisoblash modelidagi operatsiyalar soni kirish oqimidagi butun sonlar sonidagi polinom bilan cheklangan va algoritm tomonidan qo'llaniladigan xotira kirish o'lchamidagi polinom bilan chegaralanadi. Bu ikki xususiyatga ega bo‘lgan har qanday algoritmni Tyuring mashinasida arifmetik amallarni bajarish uchun tegishli algoritmlar bilan arifmetik amallarni almashtirish orqali ko‘p nomli vaqt algoritmiga keltirish mumkin. Yuqoridagi talablarning ikkinchisi bajarilmasa, bu endi to'g'ri bo'lmaydi. Butun son (Tyuring mashinasida n ga proportsional xotirani egallaydi) berilgan bo‘lsa, uni takroriy darajaga ko‘tarish yordamida n ta amalda hisoblash mumkin. Biroq, xotira ifodalash uchun ishlatiladi 2 2 n (\ displaystyle 2 ^ (2 ^ (n))), ga mutanosib 2 n (\ displaystyle 2 ^ (n)), va u kirish uchun ishlatiladigan xotiraga polinom emas, balki eksponensial jihatdan bog'liq. Demak, Tyuring mashinasida bu hisoblarni ko'pnomli vaqtda bajarish mumkin emas, lekin ko'p nomli arifmetik amallarni bajarish mumkin.Aksincha, Tyuring mashinasining qadamlar sonida ishlaydigan, ikkilik kodli kiritishning polinom uzunligi bilan chegaralangan, lekin arifmetik amallar sonida ishlamaydigan, sonlar sonidagi polinom bilan cheklangan algoritmlar mavjud. kiritish. Agar algoritm polinom vaqtida ishlasa, lekin qat'iy polinom vaqtida emas, deyiladi. zaif polinom vaqti... Kuchsiz ko'phadli algoritmi ma'lum bo'lgan, lekin qat'iy ko'phadli algoritmi noma'lum bo'lgan masalaning taniqli misoli chiziqli dasturlashdir. Zaif polinom vaqtini psevdo polinom vaqti bilan aralashtirib yubormaslik kerak. Qiyinchilik sinflari.Polinom vaqt tushunchasi hisoblash murakkabligi nazariyasida bir necha murakkablik sinflariga olib keladi. Polinom vaqti yordamida aniqlangan ba'zi muhim sinflar quyida ko'rsatilgan. : Polinom vaqtida deterministik Tyuring mashinasida echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi. : Polinom vaqtida deterministik bo'lmagan Tyuring mashinasida echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi. ZPP: Polinom vaqtida ehtimolli Tyuring mashinasida nol xato bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi. : Polinom vaqtida ehtimolli Tyuring mashinasida bir tomonlama xatolar bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik klassi. Download 296.98 Kb. Do'stlaringiz bilan baham: 
|