Algoritmlarni loyhalash
Algoritmning samaradorlik ko’rsatkichlari
tải về 207.44 Kb.
|
| Algoritmning samaradorlik ko’rsatkichlari
1. To'g'ri ishlash: Algoritmning samaradorligi, to'g'ri ishlashni ko'rsatadi. Bu, algoritmning har bir qadamini to'g'ri bajarish orqali ma'lumotlarni to'g'ri hisoblashga imkon beradi. 2. Ishonchli bo'lish: Samaradorlik, ishonchli bo'lishni talab qiladi. Algoritmning to'g'ri ishlashi uchun, dasturchi va foydalanuvchilar bu algoritmdan ishonchli bo'lishlari kerak. 3. Ishonchli ma'lumotlar: Samarador algoritm, ishonchli ma'lumotlar bilan ishlashni talab qiladi. Bu, algoritmda ishlatilayotgan ma'lumotlarning to'g'ri, aniq va to'liq bo'lishini ta'minlashga yordam beradi. 4. Tog'ri va aniqligi: Samarador algoritm, har bir qadamni to'g'ri va aniqligiga e'tibor qaratadi. Bu, algoritmda xatoliklar yuzaga kelmasligi va natijalarning aniq bo'lishi yordam beradi. 5. Yoritish: Samarador algoritm, yoritishni ta'minlashni talab qiladi. Bu, dasturchi va foydalanuvchilar uchun algoritmda qanday ishlov berishlarini tushuntirishda yordam beradi. 6. Ishonchli va to'g'ri natijalar: Samarador algoritm, ishonchli va to'g'ri natijalarni ta'minlashni talab qiladi. Bu, algoritmda aniqlanmagan xatoliklar yuzaga kelmasligi va natijalar to'liq va to'g'ri bo'lishi yordam beradi. 7. Tezlik: Samarador algoritm, tezlikni ham ko'rsatadi. Bu, algoritmda ishlov berishning tezligini oshirish yordam beradi va ishlab chiqishning tezligini ham oshiradi. 8. Murakkabligi: Samarador algoritm, murakkabligini ham aniqlashni talab qiladi. Bu, algoritmda ishlatilayotgan ma'lumotlar soni, qadam soni va boshqa faktorlar kabi muhim narsalarni ko'rsatish yordam beradi. Bitta masalani hal qilish uchun turli xil algoritmlarni ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, biz hisoblashning qaysi turidan foydalanilganligi to'g'risida kelishib olishimiz kerak .. Algoritmning ishlash vaqti bilan biz bajaradigan elementar qadamlar sonini tushunamiz. Aytaylik, psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab qilinadi (masalan, ba'zi murakkab harakatlarning og'zaki tavsifi bo'lmasa - masalan, "hamma nuqtalarni x-koordinata bo'yicha saralash"). Qo'ng'iroq qilish (qo'ng'iroq qilish) protsedurasini (ma'lum miqdordagi operatsiyalarni oladi) va uning bajarilishini (bajarilishini) farqlashingiz kerak, ular uzoq davom etishi mumkin. Algoritmning murakkabligi bu vazifaning o'lchamiga qarab talab qilinadigan manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira) aks ettiradigan qiymatdir. Shunday qilib, biz algoritmning vaqtinchalik T (n) va fazoviy V (n) murakkabligini ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ham shunga o'xshash tarzda baholanadi. Baholashning eng oson usuli bu eksperimental usul, ya'ni algoritmni dasturlash va natijada olingan dasturni bir nechta vazifalar bo'yicha bajarish, dasturlarning bajarilish vaqtini baholash. Biroq, bu usul bir qator kamchiliklarga ega. Birinchidan, eksperimental dasturlash, ehtimol qimmat jarayon. Ikkinchidan, shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga quyidagi omillar ta'sir qiladi: 1. Dastur algoritmining vaqt murakkabligi; 2. Bajariladigan dasturning kompilyatsiya qilingan kodining sifati; 3. Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari. Ikkinchi va uchinchi omillarning mavjudligi algoritmning vaqt murakkabligini o'lchashning tipik birliklaridan foydalanishga imkon bermaydi (soniya, millisekundlar va boshqalar), chunki agar siz turli xil dasturchilar (har bir algoritmni kim dasturlasa) bir xil algoritm uchun har xil baholarni olish mumkin. o'z), turli xil kompilyatorlar va turli xil kompyuterlar. Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq. Odatda algoritmning vaqt murakkabligi n o'lchamidagi kirish ma'lumotlarini T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga murojaat qilishadi. Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini nazariy jihatdan hisoblaydigan usul mavjud. Murakkablikning o'sishi tartibi (yoki aksiomatik murakkablik) katta kirish o'lchamiga ega bo'lgan algoritmning murakkablik funktsiyasining taxminiy xatti-harakatlarini tavsiflaydi. Bundan kelib chiqadiki, vaqtning murakkabligini baholashda elementar operatsiyalarni ko'rib chiqishga hojat yo'q, algoritmning bosqichlarini ko'rib chiqish kifoya qiladi. Algoritmning bosqichi bu ketma-ket joylashgan elementar operatsiyalar to'plami bo'lib, ularning bajarilish vaqti kirish hajmiga bog'liq emas, ya'ni u yuqorida qandaydir doimiy bilan chegaralangan. Algoritmning murakkabligini o'lchashning bir necha usullari mavjud. Dasturchilar odatda algoritm tezligiga e'tibor qaratishadi, ammo boshqa ko'rsatkichlar ham bir xil ahamiyatga ega - xotira hajmiga, diskdagi bo'sh joyga talablar. Tez algoritmdan foydalanish, agar kompyuter ishlashi kerak bo'lganidan ko'proq xotirani talab qilsa, kutilgan natijalarga olib kelmaydi. Xotira yoki vaqt. Ko'pgina algoritmlar xotira hajmi va tezligi o'rtasida tanlovni taklif qiladi. Muammoni tezroq, katta hajmdagi xotiradan foydalangan holda yoki ozroq hajmni olib, sekinroq hal qilish mumkin. Bu holatda odatiy misol eng qisqa yo'llarni qidirish algoritmi hisoblanadi. Tarmoq shaklida shahar xaritasini taqdim etib, siz ushbu tarmoqning har qanday ikkita nuqtasi orasidagi eng qisqa masofani aniqlash uchun algoritm yozishingiz mumkin. Bu masofalarni kerak bo'lganda hisoblamaslik uchun barcha nuqtalar orasidagi eng qisqa masofani ko'rsatib, natijalarni jadvalga saqlashimiz mumkin. Berilgan ikkita nuqta orasidagi eng qisqa masofani aniqlashimiz kerak bo'lsa, bizshunchaki jadvalning tugagan masofasini olishimiz mumkin. Natija bir zumda olinadi, ammo bu juda katta hajmdagi xotirani talab qiladi. Katta shahar xaritasida o'n minglab fikrlar bo'lishi mumkin. Keyin, yuqorida tavsiflangan jadvalda 10 milliarddan ortiq hujayralar bo'lishi kerak. Bular Algoritmning ishlashini yaxshilash uchun qo'shimcha 10 Gb xotirani ishlatish kerak. Ushbu qaramlikdan kosmik-vaqt murakkabligi g'oyasi kelib chiqadi. Ushbu yondashuv bilan, algoritm bajarilihtezligi va iste'mol qilinadigan xotira nuqtai nazaridan baholanadi. Vaqtinchalik murakkablikka e'tiborni qaratamiz, ammo shunga qaramay, biz iste'mol qilingan xotiraning hajmini aniq belgilaymiz. Turli xil algoritmlarni taqqoslashda ularning murakkabligi kirish ma'lumotlari miqdoriga bog'liqligini bilish muhimdir. Masalan, bitta usul yordamida saralashda ming sonlarni qayta ishlash 1 s., Va million sonlarni qayta ishlash uchun 10 s vaqt kerak bo'ladi, boshqa algoritmdan foydalanish esa 2 s vaqtni talab qilishi mumkin. va 5 s. navbati bilan Bunday sharoitda qaysi algoritm yaxshiroq ekanligini aniq aytish mumkin emas. Umumiy holda, algoritmning murakkabligini kattalik tartibida baholash mumkin. Agar kirish ma'lumotlarining o'lchamlari oshgani sayin, algoritmning bajarilish vaqti f (N) funktsiyasi bilan bir xil tezlikda oshsa, algoritmda O (f (n)) murakkablik bor. A [NxN] matritsasi uchun har bir satrda maksimal elementni topadigan kodni ko'rib chiqing. for i:=1 to N do begin max:=A[i,1]; for j:=1 to N do begin if A[i,j]>max then max:=A[i,j Ushbu algoritmda i o'zgaruvchisi 1 dan N.gacha o'zgaradi, i ning har bir o'zgarishi bilan birga, j o'zgaruvchisi ham 1 dan N ga o'zgaradi. Tashqi aylanishning har bir N takrorlanishida ichki pastadir ham N marta bajariladi. Ichki pastadir takrorlanishlarining umumiy soni N * N dir. Bu O (N ^ 2) algoritmining murakkabligini aniqlaydi. Algoritmning murakkablik tartibini taxmin qilishda faqat eng tez o'sadigan qismda foydalanish kerak. Vazifalar aylanishi N ^ 3 + N ifodasi bilan tasvirlangan deb taxmin qiling. Bunday holda, uning murakkabligi O ga teng bo'ladi (N ^ 3). Funktsiyaning tez o'sib boruvchi qismini ko'rib chiqish, algoritmning xatti-harakatlarini N ning ortishi bilan baholashga imkon beradi. Masalan, N = 100 bilan N ^ 3 + N = 1000100 va N = 1000000 o'rtasidagi farq atigi 100 ga teng, bu 0,01%. O ni hisoblashda, ifodalarda doimiy omillarga e'tibor bermaslik mumkin. 3N ^ 3 ish bosqichiga ega bo'lgan algoritm O (N ^ 3) deb hisoblanadi. Bu O (N) nisbati muammoning hajmiga bog'liqligini yanada aniqroq qiladi. Qiyinchilikni aniqlash Dasturning eng murakkab qismlari odatda pastadir va qo'ng'iroq qilish protseduralari. Oldingi misolda butun algoritm ikki tsikl yordamida amalga oshirildi. Agar bitta protsedura boshqasini chaqirsa, u holda protseduraning murakkabligini batafsilroq baholash kerak. Agar unda muayyan miqdordagi ko'rsatmalar bajarilgan bo'lsa (masalan, bosib chiqarish), unda bu murakkablikni baholashga deyarli ta'sir qilmaydi. Agar O (N) bosqichlar chaqirilayotgan protsedurada bajarilsa, funktsiya algoritmni sezilarli darajada murakkablashtirishi mumkin. Agar protsedura ko'chadan ichkarisiga chaqirilsa, u holda ta'sir yanada katta bo'lishi mumkin. Misol tariqasida ikkita protsedurani ko'rib chiqing: O (N ^ 3) murakkabligi bilan sekin va O (N ^ 2) murakkabligi bilan. Algoritm murakkabligining asosiy ko'rsatkichi muammoni hal qilish uchun zarur bo'lgan vaqt va talab qilinadigan xotira miqdori hisoblanadi. Shuningdek, topshiriqlar sinfi uchun murakkablikni tahlil qilganda ma'lum bir ma'lumotni - kirish hajmini tavsiflovchi ma'lum bir raqam aniqlanadi . Shunday qilib, algoritmning murakkabligi kirish hajmining funktsiyasi degan xulosaga kelishimiz mumkin . Algoritmning murakkabligi bir xil kirish hajmi bilan farq qilishi mumkin, ammo har xil kirish ma'lumotlari. Eng yomon , o'rta yoki eng yaxshi holatda murakkablik tushunchalari mavjud . Odatda, eng yomon ishning murakkabligi baholanadi. Vaqtning murakkabligi eng yomon holatda, berilgan o'lchamdagi masalani echishda algoritmni bajarish paytida bajariladigan operatsiyalarning maksimal soniga teng bo'lgan kirish hajmining funktsiyasi. Eng yomon holatda, kapasitiv murakkablik bu o'lchamdagi muammolarni echishda foydalanilgan xotira hujayralarining maksimal soniga teng kirish hajmi funktsiyasidir. Algoritmlarning murakkabligini aniqlash uchun, algoritmda ishlatiladigan operatsiyalar soni, o'zaro aloqadorliklar soni va algoritmning ishga tushirish vaqti kabi ma'lumotlarni olish kerak. Bunday ma'lumotlar, algoritmlarning murakkabligini tushunish va optimallashtirish uchun juda muhimdir. Murakkab algoritmlar, ishga tushirish vaqti va resurslarni ko'p sarflaydi, shuning uchun optimallashtirish kerak bo'ladi. Hisoblash qobiliyati. Ko'plab muammolarda uchraydigan yana bir xususiyat - bu ularning asosan diskretligi. Ko'plab muammolarda uchraydigan yana bir xususiyat-bu ularning asosiy ajralib turishi. Boshqacha qilib aytganda, bu shunday masalalarki, ularda yechim kombinatorial variantlarning keng to'plamidan qidirib topiladi; maqsad aniq belgilangan shartlarni qanoatlantiradigan echimni samarali topishdir. Hisoblash samaradorligi tushunchasini aniqlash uchun, biz birinchi navbatda ish vaqtining samaradorligiga e'tibor qaratamiz: algoritmlar tez ishlashi kerak. Ammo algoritmlar boshqa resursrlardan foydalanish nuqtai nazaridan ham samarali bo'lishi mumkinligini tushunish muhimdir. Xususan, algoritm tomonidan ishlatilinadigan xotira miqdori ham samaradorlikning muhim jixati bo'lishi mumkin. Algoritmning hisoblash qobiliyati, algoritmda ishlatiladigan operatsiyalar soni va o'zaro aloqadorliklar soni bilan belgilanadi. Bu qobiliyat, algoritmda ishlatilgan operatsiyalar va o'zaro aloqadorliklar soni ko'paytikca, algoritmdagi hisoblash jarayoni murakkablashadi. Shuning uchun, algoritmlar hisoblash qobiliyati ko'paytikca murakkablashadi va ishga tushirish vaqti ham ko'payadi. Hisoblash qobiliyati, algoritmlarni optimallashtirish uchun muhim ma'lumotlardan biridir. Va nihoyat, yana bir izoh. Samaradorlik va murakkablik talabi ko‘pincha bir-biri bilan ziddiyatga kirishadi. Bu mutlaqo tabiiy. Axir, mashina sotib olayotgan bo‘lsangiz, eng chiroyli va qulay mashinaning eng arzon bo‘Iishiga umid qilmaysiz. Algoritmlashda ham shunday. Agar sizga juda samarador algoritm kerak bo‘lsa, bu algoritm boshqalariga nisbatan ancha murakkabroq bo’lishi ehtimoli katta. Amaliyotda esa oqilona murosaga kelishga to ‘g‘ri keladi. Algoritmni baholashda tekis solishtirma mezonlari: 1. Ishlatilayotgan ma'lumotlar soni: Algoritmning murakkabligini aniqlash uchun, ishlatilayotgan ma'lumotlar soni katta bo'lsa, bu algoritmda ko'p qadam va hisoblashlar amalga oshirishi mumkin. Bunday holatda, murakkabligi yuqori bo'ladi. 2. Qadam soni: Algoritmning murakkabligi, ishlatilayotgan qadam soniga bog'liq bo'ladi. Agar algoritm ko'p qadamli bo'lsa, bu murakkabligini oshiradi. 3. Boshqa faktorlar: Algoritmda foydalanilayotgan boshqa faktorlar, masalan, ishlatilayotgan dasturlash tillari yoki ko'rsatilayotgan ma'lumotlarning turi ham murakkabligi ta'sir etishi mumkin. Bularning har biri algoritmlarning murakkabligini baholashda muhim hisoblanadi. Shuningdek, murakkablikni kamaytirish uchun optimallashtirish va boshqa yondashuvlar ham foydali bo'ladi. Mavjud algoritmlarning ko’pchilig xotira va tezlik o’rtasida tanlovni taklif qiladi. Masala tez ishlashi va katta xotira egallashi yoki sekin ishlashi va kichik xotira hajmini egallashi mumkin. Bu holatda eng odatiy misollardan biri eng qisqa masofani topish masalasi bo’la oladi. Bunda siz o’zaro bog’liq bo’lgan shahar orasidagi istalgan ikki nuqta orasidagi eng qisqa masofani topishingiz kerak bo’ladi. Bunda biz barcha nuqtalar orasidagi qisqa masofalarni aniqlab ularni jadval shaklida saqlab qo’yishimiz mumkin. Va biz eng qisqa masofani aniqlashimizga to’g’ri kelganda shunchaki jadvaldan ma’lumotni olib qo’yishimiz mumkin bo’ladi. Natijani shu zahoti olishimiz mumkin, ammo bu juda katta hajm talab qiladi. Masalan biror katta xaritada 10 minglab nuqtalar bo’lishi mumkin va bizning jadvalimiz buning uchun 10 milliarddan ortiq ma’lumotni saqlashiga to’g’ri keladi va bu taxminan 10GB ga yaqin xotirani band etishi mumkin. Ushbu holatdan hajm-vaqt murakkabligi kelib chiqadi. Shunda algoritm vaqt bo’yicha ishlash tezligi yoki hajm bo’yicha ishlash tezligi bilan baholanadi. Biz asosiy e’tiborni vaqt bo’yicha murakkablikka qaratamiz lekin shu bilan birga foydalaniladigan xotira hajmini ham aniq belgilashimizga to’g’ri keladi. Logarifmik solishtirma mezonlari, algoritmlarning murakkabligini baholashda katta ahamiyatga ega. Bu mezonlar, algoritmlarning ishga tushirish vaqti va xotirani kamaytirishda yordam beradi. Algoritmlarning murakkabligini oshirish uchun, logarifmik solishtirma mezonlari, qidiruvchi algoritmlar va sortirovka algoritmlari kabi ko'p maqsadli algoritm turlarida foydalaniladi. Logarifmik solishtirma mezonlari, ma'lumotlar sonining kattaligiga nisbatan murakkabligi kamaytiriladi. Bunday mezonlar, ma'lumotlar soni kattalashtikda ham murakkablikni oshirmaydi. Misol uchun, bir massivni tartiblashda yoki bir elementni qidirishda logarifmik solishtirma mezonlariga e'tibor qaratiladi. Logarifmik solishtirma mezonlari, O(log n) shaklida ifodalangan. Bu shaklda "n" ma'lumotlar sonini anglatadi. Bunda "log" esa logarifmni ifodalaydi. Shuning uchun, algoritmlar murakkabligi O(log n) bo'lgan paytda yaxshi natijalar ko'rsatadi. tải về 207.44 Kb. Chia sẻ với bạn bè của bạn:
|