|
O’zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi osiyo xalqaro universitetining
|
| bet | 6/7 | | Sana | 16.12.2023 | | Hajmi | 137,71 Kb. | | #120571 |
Bog'liq Bayer va mur algoritimlari2.3 Algoritmlarni tashlil qilish
Yilda Kompyuter fanlari, algoritmlarni tahlil qilish ni topish jarayoni hisoblash murakkabligi algoritmlar - vaqt, saqlash yoki boshqa manbalar miqdori ularni ijro eting. Odatda, bu a ni o‘z ichiga oladi funktsiya algoritm kiritish uzunligini va uni bajaradigan qadamlar soniga bog‘laydigan (uning vaqtning murakkabligi) yoki u foydalanadigan saqlash joylari soni (uning kosmik murakkablik). Algoritm ushbu funktsiya qiymatlari kichik bo‘lganda yoki kirish hajmining o‘sishiga nisbatan sekin o‘sganda samarali bo‘ladi deyiladi. Xuddi shu uzunlikdagi turli xil yozuvlar algoritmning xatti-harakatlariga olib kelishi mumkin, shuning uchun eng yaxshi, eng yomon va o‘rtacha ish tavsiflarning barchasi amaliy qiziqish uyg‘otishi mumkin. Agar boshqacha ko‘rsatilmagan bo‘lsa, algoritmning ishlashini tavsiflovchi funktsiya odatda yuqori chegara, algoritmga eng yomon holatlardan aniqlandi.
"Algoritmlarni tahlil qilish" atamasi tomonidan kiritilgan Donald Knuth. Algoritmni tahlil qilish keng doiraning muhim qismidir hisoblash murakkabligi nazariyasi, bu berilganni hal qiladigan har qanday algoritm uchun zarur bo‘lgan manbalar uchun nazariy baholarni beradi hisoblash muammosi. Ushbu taxminlar izlashning oqilona yo‘nalishlari to‘g‘risida tushuncha beradi samarali algoritmlar.Algoritmlarni nazariy tahlil qilishda ularning murakkabligini asimptotik ma'noda baholash, ya'ni o‘zboshimchalik bilan katta kirish uchun murakkablik funktsiyasini baholash odatiy holdir. Big O notation, Katta-omega yozuvlari va Big-teta yozuvi shu maqsadda ishlatiladi. Masalan; misol uchun, ikkilik qidirish qidirilayotgan tartiblangan ro‘yxat uzunligining logarifmiga mutanosib bo‘lgan bir necha bosqichda yoki O (log (n)) da, so‘zma-so‘z " logaritmik vaqt". Odatda asimptotik taxminlar har xil bo‘lgani uchun ishlatiladi amalga oshirish bir xil algoritm samaradorligi bilan farq qilishi mumkin. Ammo berilgan algoritmni istalgan ikkita "oqilona" amalga oshirish samaradorligi a deb nomlangan doimiy multiplikativ omil bilan bog‘liq. yashirin doimiy.
Ba'zida samaradorlikning aniq (asimptotik bo‘lmagan) o‘lchovlari hisoblab chiqilishi mumkin, ammo ular odatda algoritmni amalga oshirishda ma'lum taxminlarni talab qiladi, deyiladi hisoblash modeli. Hisoblash modeli an nuqtai nazaridan aniqlanishi mumkin mavhum kompyutermasalan, Turing mashinasi, va / yoki ma'lum bir operatsiyalar birlik vaqtida bajarilishini e'lon qilish orqali, masalan, agar biz ikkilik qidiruv qo‘llanadigan tartiblangan ro‘yxatda n va biz ro‘yxatdagi elementni har bir qidirishni birlik vaqtida, so‘ngra eng ko‘p jurnalda bajarilishi mumkinligiga kafolat beramiz2 n Javobni qaytarish uchun + 1 marta birlik kerak.Vaqt samaradorligini baholash biz qadam deb belgilagan narsaga bog‘liq. Tahlilning haqiqiy bajarilish vaqtiga foydali bo‘lishi uchun qadamni bajarish uchun zarur bo‘lgan vaqt yuqorida doimiy bilan chegaralangan bo‘lishi kafolatlanishi kerak. Bu erda ehtiyot bo‘lish kerak; masalan, ba'zi tahlillar ikkita raqamning qo‘shilishini bitta qadam deb hisoblaydi. Ushbu taxmin ba'zi kontekstlarda kafolatlanmasligi mumkin. Masalan, hisoblashda ishtirok etadigan raqamlar o‘zboshimchalik bilan katta bo‘lishi mumkin bo‘lsa, bitta qo‘shish uchun zarur bo‘lgan vaqt endi doimiy deb qabul qilinmaydi.
Odatda ikkita iqtisodiy model qo‘llaniladi:
The yagona xarajat modelideb nomlangan yagona narxlarni o‘lchash (va shunga o‘xshash farqlar), har bir mashinaning ishlashiga, ishtirok etadigan raqamlarning kattaligidan qat'i nazar, doimiy xarajatlarni belgilaydi
The logaritmik xarajatlar modelideb nomlangan logaritmik xarajatlarni o‘lchash (va shunga o‘xshash farqlar), har bir mashinaning ishlashiga sarflangan bitlar soniga mutanosib narx belgilaydiIkkinchisini ishlatish ancha noqulay, shuning uchun u faqat kerak bo‘lganda, masalan, tahlil qilishda ishlaydi ixtiyoriy aniqlikdagi arifmetika ishlatiladigan algoritmlar kabi kriptografiya.Tez-tez e'tibordan chetda qoladigan muhim nuqta shundaki, muammolar uchun nashr etilgan pastki chegaralar ko‘pincha amalda ishlatishingiz mumkin bo‘lgan operatsiyalar to‘plamidan ko‘ra cheklangan hisoblash modeli uchun beriladi va shuning uchun sodda bo‘lganidan tezroq algoritmlar mavjud. mumkin deb o‘yladim.
Ish vaqti tahlili
Ish vaqtini tahlil qilish - bu o‘sishni taxmin qiladigan va taxmin qiladigan nazariy tasnif ish vaqti (yoki ish vaqti) ning algoritm uning kabi kirish hajmi (odatda sifatida belgilanadi n) ortadi. Ish vaqti samaradorligi - bu juda katta qiziqish uyg‘otadigan mavzu Kompyuter fanlari: A dastur qaysi algoritmni amalga oshirishiga qarab bajarilishi bir necha soniya, soat yoki hatto yillar davom etishi mumkin. Esa dasturiy ta'minotni profillashtirish algoritmning ishlash vaqtini amalda o‘lchash uchun texnikadan foydalanish mumkin, ular barcha cheksiz ko‘p kirishlar uchun vaqt ma'lumotlarini bera olmaydi; ikkinchisiga faqat ish vaqtini tahlil qilishning nazariy usullari bilan erishish mumkin.
Ampirik metrikalarning kamchiliklari
Algoritmlar mavjud bo‘lganligi sababli platformadan mustaqil (ya'ni berilgan algoritm o‘zboshimchalik bilan amalga oshirilishi mumkin) dasturlash tili o‘zboshimchalik bilan kompyuter o‘zboshimchalik bilan ishlash operatsion tizim) ni ishlatishda qo‘shimcha muhim kamchiliklar mavjud empirik berilgan algoritmlar to‘plamining qiyosiy ko‘rsatkichlarini baholashga yondashish.Masalan, a-da ma'lum bir yozuvni qidiradigan dasturni oling saralangan ro‘yxat hajmi n. Aytaylik, ushbu dastur a-dan foydalangan holda eng zamonaviy kompyuter A Computer-da amalga oshirildi chiziqli qidiruv algoritmi va kompyuter B-da juda sekin ishlaydigan mashina ikkilik qidiruv algoritmi. Sinov sinovi o‘z dasturlarini boshqaradigan ikkita kompyuterda quyidagilar ko‘rinishi mumkin:
n (ro‘yxat hajmi) Kompyuter ish vaqti
(ichida.) nanosaniyalar) Kompyuter B ish vaqti
(ichida.) nanosaniyalar)
Ushbu ko‘rsatkichlarga asoslanib, shunday xulosaga kelish oson bo‘lar edi Kompyuter A samaradorligi jihatidan ancha ustun bo‘lgan algoritmni ishlaydi Kompyuter B. Ammo, agar kirish ro‘yxati hajmi etarlicha ko‘paytirilsa, bu xulosa keskin xatoga yo‘l qo‘yilganligini ko‘rsatadi:
n (ro‘yxat hajmi) Kompyuter ish vaqti
(ichida.) nanosaniyalar) Kompyuter B ish vaqti
(ichida.) nanosaniyalar)
Chiziqli qidiruv dasturini boshqaradigan A kompyuter, a ni namoyish etadi chiziqli o‘sish sur'ati. Dasturning ishlash vaqti uning kirish hajmiga to‘g‘ri proportsionaldir. Kirish hajmini ikki baravar oshirish ish vaqtini ikki baravar oshiradi, kirish hajmini to‘rt baravar oshirish ish vaqtini to‘rt baravar oshiradi va hokazo. Boshqa tomondan, B ikkilik qidiruv dasturini ishga tushirgan kompyuter B a ni namoyish etadi logaritmik o‘sish sur'ati. Kirish hajmini to‘rt baravar oshirish faqat ish vaqtini a ga oshiradi doimiy miqdori (ushbu misolda, 50,000 ns). A kompyuter go‘yoki tezroq mashina bo‘lsa ham, B kompyuteri ish vaqtida muqarrar ravishda A kompyuterni ortda qoldiradi, chunki u o‘sish sur'ati ancha past bo‘lgan algoritm bilan ishlaydi.Berilgan algoritmning eng yomon stsenariysi uchun ish vaqti murakkabligi ba'zan algoritmning tuzilishini o‘rganish va ba'zi soddalashtirilgan taxminlarni kiritish orqali baholanishi mumkin. Quyidagilarni ko‘rib chiqing psevdokod:
1 kirishdan n ning musbat tamsayıini oling2 agar n> 103 chop etish "Bu biroz vaqt olishi mumkin ..." 4 uchun i = 1 ga n5 uchun j = 1 ga i6 chop etish i * j7 chop etish "Bajarildi!"
Berilgan kompyuter a ni oladi diskret vaqt har birini bajarish uchun ko‘rsatmalar ushbu algoritmni bajarish bilan bog‘liq. Berilgan ko‘rsatmani bajarish uchun ma'lum vaqt miqdori qaysi ko‘rsatma bajarilayotganiga va qaysi kompyuter uni bajarayotganiga qarab o‘zgaradi, ammo an'anaviy kompyuterda bu miqdor bo‘ladi deterministik.[9] 1-bosqichda bajarilgan harakatlar vaqtni sarflaydi deb ayting T1, 2-qadam vaqtdan foydalanadi T2, va hokazo.
Yuqoridagi algoritmda 1, 2 va 7 bosqichlar faqat bir marta bajariladi. Eng yomon vaziyatni baholash uchun 3-qadam ham bajarilishini taxmin qilish kerak. Shunday qilib, 1-3 va 7-bosqichlarni bajarish uchun umumiy vaqt miqdori:
T_ {1} + T_ {2} + T_ {3} + T_ {7}. ,
The ko‘chadan 4, 5 va 6-bosqichlarda hiyla-nayrangni baholash kerak. 4-bosqichda tashqi tsikl testi bajariladi ( n + 1) marta (for loopini tugatish uchun qo‘shimcha qadam kerakligini unutmang, shuning uchun n + 1 emas, balki n) T4( n + 1) vaqt. Ichki halqa esa j qiymati bilan boshqariladi, bu takrorlanadi 1 dan men. Tashqi halqa orqali birinchi o‘tish paytida j 1 dan 1 gacha takrorlanadi: Ichki tsikl bitta o‘tishni amalga oshiradi, shuning uchun ichki halqa tanasini (6-qadam) ishlatish sarf qiladi T6 vaqtni va ichki pastadir sinovi (5-qadam) 2 ni sarflaydiT5 vaqt. Tashqi tsikldan keyingi o‘tish paytida j 1 dan 2 gacha takrorlanadi: ichki tsikl ikkita o‘tishni amalga oshiradi, shuning uchun ichki tsikl tanasini (6-qadam) boshqarishda 2 ta sarflanadiT6 vaqt, va ichki pastadir sinovi (5-qadam) 3ni iste'mol qiladi vaqt.
Boshqa resurslarning o‘sish sur'atlari tahlili
Ish vaqtini tahlil qilish metodologiyasidan iste'molning o‘sishi kabi boshqa o‘sish sur'atlarini bashorat qilish uchun ham foydalanish mumkin xotira maydoni. Misol tariqasida, dastur hajmi bo‘yicha xotiradan foydalanishni boshqaradigan va qayta taqsimlaydigan quyidagi psevdokodni ko‘rib chiqing. fayl ushbu dasturni boshqaradigan:
esa fayl hali ham ochiq: ruxsat bering n = fayl hajmi uchun har 100000 kishi kilobayt fayl hajmining oshishi ajratilgan xotira hajmini ikki baravar oshirish Bunday holda, n hajmi kattalashgan sari xotira an da sarflanadi eksponent o‘sish stavkasi, bu buyurtma O (2n). Bu xotira iste'moli uchun juda tez va ehtimol boshqarib bo‘lmaydigan o‘sish sur'ati resurslar.
Dolzarbligi
Algoritm tahlili amalda muhim ahamiyatga ega, chunki samarasiz algoritmdan tasodifiy yoki bexosdan foydalanish tizim ishiga sezilarli ta'sir ko‘rsatishi mumkin. Vaqtni sezgir bo‘lgan dasturlarda uzoq vaqt davomida ishlaydigan algoritm natijalarini eskirgan yoki foydasiz holga keltirishi mumkin. Shuningdek, samarasiz algoritm ishlash uchun tejashga yaroqsiz miqdordagi hisoblash quvvati yoki saqlashni talab qilib, uni deyarli foydasiz holga keltirishi mumkin.
Doimiy omillar
Algoritmlarni tahlil qilish odatda asimptotik ko‘rsatkichlarga, xususan, boshlang‘ich darajaga qaratiladi, ammo amaliy qo‘llanmalarda doimiy omillar muhim ahamiyatga ega va haqiqiy ma'lumotlar amalda har doim ham cheklangan hajmga ega. Chegara odatda manzilli xotiraning o‘lchamiga teng, shuning uchun 32-bitli mashinalarda 232 = 4 GiB (agar katta bo‘lsa segmentlangan xotira va 64-bitli mashinalarda 2)64 = 16 EiB. Shunday qilib cheklangan kattalik berilgan holda, o‘sish tartibi (vaqt yoki makon) doimiy omil bilan almashtirilishi mumkin va shu ma'noda barcha amaliy algoritmlar etarlicha katta doimiy yoki etarli bo‘lmagan ma'lumotlar uchun O (1) dir.Ushbu talqin birinchi navbatda juda sekin o‘sadigan funktsiyalar uchun foydalidir: (ikkilik) takroriy logarifma (log*) barcha amaliy ma'lumotlar uchun 5 dan kam (265536 bit); (ikkilik) log-log (log log.) n) deyarli barcha amaliy ma'lumotlar uchun 6 dan kam (264 bit); va ikkilik jurnal (log n) deyarli barcha amaliy ma'lumotlar uchun 64 dan kam (264 bit). Doimiy bo‘lmagan murakkablikka ega algoritm, shunga qaramay, amaliy ma'lumotlarning doimiy murakkabligi bo‘lgan algoritmga qaraganda samaraliroq bo‘lishi mumkin, agar doimiy vaqt algoritmining ustuni katta doimiy omilga olib keladigan bo‘lsa, masalan, K> k log log n shunday ekan K / k> 6 va n
Katta ma'lumotlar uchun chiziqli yoki kvadratik omillarni e'tiborsiz qoldirib bo‘lmaydi, ammo kichik ma'lumotlar uchun asimptotik samarasiz algoritm samaraliroq bo‘lishi mumkin. Bu, ayniqsa, ishlatiladi gibrid algoritmlar, kabi Timsort, unda asimptotik jihatdan samarali algoritm ishlatiladi (bu erda birlashtirish, vaqt murakkabligi bilan n log n), lekin asimptotik samarasiz algoritmga o‘ting (bu erda qo‘shish tartibi, vaqt murakkabligi bilan n ^ {2}) kichik ma'lumotlar uchun, chunki oddiyroq algoritm kichik ma'lumotlarda tezroq bo‘ladi.
XULOSA Hozirgi axborotlashgan jamiyatda axborot va uning oqimi tez sur`atlarda o`sib bormoqda. Internetda ko`plab axborot manbalari, ya`ni megadatalar, bigdatalar o`lchami oshib bormoqda. Bularni saqlash, saralash, foydalanish muammolarni keltirib chiqarishi mumkin. Axborotlarning bir vaqtda bir kanalda bo`lishi, bir vaqtda uzatilishi muammolarni keltirib chiqarishi mumkin. Shu sababli ularni tartibga solishni ma`lum bir usulni, ya`ni tartiblash va saralash usulini talab etadi. Bular esa o`z navbatida algoritmni, vazifalar hamda malalarni bosqichma-bosqich yechishni ko`zda tutadi. Ayni damda axborotlarni izlash, dasturlarda turli masalarni yechish maqsadida turli algoritmlar ishlab chiqarildi. Yuqorida xuddi shunday algoritmlardan Boyer-mur algoritmi tahlil qilindi. Ushbu usul axborotlarni izlash va saralash soxasida eng samarali usul hisoblanadi. Boyer-Mur algoirtmi izlashda satr bo`yicha kerakli axborotni uzatishni taklif etadi. Yuqorida shunga doir misollar ham keltirilgan. Algoritmlar doim ham bir-biridan tubdan farq qilmaydi. Ze`ro, turli algoritm bir masalani yechishga qaratilgan bo`lishi mumkin.
|
| |
