O’zbekiston Respublikasi Axborot Texnologiyalari va Kommunikatsiyalarini Rivojlantirish Vazirligi Muhammad al- Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti Mavzu : Algoritmlarni loyihalash. Algoritm korrekt va samaradorligini baholash. Kvadrat tenglama ildizlarini aniqlash algoritmi. Uchburchak yuzasi uchun Geron formulasi Topshirdi : 021-21 guruh talabasi __
Reja: I.Kirish 1.Algoritm tushunchasi va uning ta’rifi. 2.Algoritmlarni baholash. 3. Algoritmlarni tahlil qilish ; eng yaxshi, eng yomon va o'rtacha ish vaqti.
Kirish. Har qanday dasturchi uchun algoritmlar nazariyasining asoslarini bilish juda muhim, chunki algoritmlarning umumiy xususiyatlarini va ularni namoyish etish uchun rasmiy modellarni o'rganadigan fan. Hatto informatika darslaridan bizga kelajakda maktabga qaraganda murakkabroq topshiriqlarni yozishda yordam beradigan oqim jadvallarini tuzishga o'rgatiladi. Hech kimga sir emaski, deyarli har doim ma'lum bir muammoni hal qilishning bir necha yo'li mavjud : kimdir ko'p vaqt sarflashni, boshqalari resurslarni sarflashni o'z ichiga oladi, boshqalari esa deyarli echim topishga yordam beradi. Siz har doim vazifaga muvofiq, xususan, muammolar sinfini hal qilish algoritmlarini ishlab chiqishda eng maqbul variantni izlashingiz kerak. Shuningdek, algoritm turli xil hajmlar va miqdorlarning boshlang'ich qiymatlarida o'zini qanday tutishi, unga qanday resurslar kerakligi va yakuniy natijani olish uchun qancha vaqt kerakligini baholash ham muhimdir. Algoritm tushunchasi va uning ta’rifi. Ma'lumotni qayta ishlash algoritmi - bu kompyuter fanida muammoni hal qilish usulining tavsifi bo'lib, uni keyinchalik tanlangan dasturlash muhitida amalga oshirish mumkin. Algoritmni tahlil qilish - bu baholashni o'rganadigan informatika sohasidirishlash algoritmlari.
Algoritmning murakkabligi bu algoritmni tahlil qilishda hisobga olinadigan elementar operatsiyalar sonidir. A algoritmi bilan belgilangan operatsiyalarning eng ko'p soni og'irlikning eng yomon holati bo'lib, u ma'lum bir o'lchovdagi D kirishlarni kiritadi. Laboriousness eng yaxshi ishi algoritm operatsiyalar kichik soni A barcha yozuvlari da bir D ma'lum o'lchov n. Laboriousness o'rtacha ishi algoritm operatsiyalar o'rtacha soni A barcha yozuvlari da bir D ma'lum o'lchov n. Algoritmning murakkabligi funktsiyasi - algoritmning murakkabligi bu D kirishidagi A parametr parametrlariga bog'liqligi. Algoritmning vaqt murakkabligi eng yomon holatga algoritmning murakkablik funktsiyasini asimptotik baholashdir.
Xotira hajmi - D kirish uchun A algoritmini amalga oshirishda ishtirok etadigan xotira joylarining maksimal soni. Algoritmning kapasitiv murakkabligi bu algoritmning eng yomon holatdagi xotira funktsiyasini asimptotik baholashdir. Algoritmning eng yomon, o'rta va eng yaxshi holatlaridagi resurslarning murakkabligi vaqt va funktsiyalar sinflarining tartiblangan juftligi.asemptomatik belgi bilan aniqlanadigan va ko'rib chiqilayotgan holatga mos keladigan sig'im murakkabligi.
Ma'lumotlar tuzilmalari bilan ishlash algoritmlari bu olinadigan asosiy tamoyillar va metodologiyani aniqlaydigan algoritmlardirma'lumotlarni qayta ishlash usullarini tushunish. Saralash algoritmlari massivlar va fayllarni tartibga solish uchun mo'ljallangan algoritmlardir. Qidiruv algoritmlari bu katta ma'lumotlar to'plamida ma'lum elementlarni qidirish uchun mo'ljallangan algoritmlar. Graf algoritmlari bu amalga oshirish uchun mo'ljallangan algoritmlardirgrafik ayirish va qidirish strategiyalari. Simlarni qayta ishlash algoritmlari bu belgilar ketma-ketligini qayta ishlash uchun bir qator usullarni o'z ichiga olgan algoritmlardir. Geometrik algoritmlar bu geometrik ob'ektlardan foydalangan holda muammolarni echish uchun algoritmlardir.
Algoritmni baholash mezonlari Og'irlikni o'lchashning yagona mezoni (RVC) algoritmning har bir bosqichi vaqtning birligida va xotira xujayrasi bitta hajm birligida (doimiyga aniq) bajarilishini taxmin qiladi. Logarifmik o'lchov mezoni (LCV) ma'lum bir operatsiya bilan ishlov berilgan operand hajmini va xotira hujayrasida saqlanadigan qiymatni hisobga oladi. LCV vaqt murakkabligi l (O p ) qiymati bilan belgilanadi , bu erda O p - operandning qiymati. LCV ning sig'im murakkabligi l (M) qiymati bilan belgilanadi, bu erda M - xotira xujayrasining kattaligi.
Umumiy qiyinchiliklarni baholash xususiyatlari Endi biz murakkablikni hisoblash uchun eng ko'p ishlatiladigan ba'zi funktsiyalarni sanab o'tamiz. Vazifalar murakkablikning ortib boradigan tartibida keltirilgan. Ushbu ro'yxatdagi funktsiya qanchalik yuqori bo'lsa, bunday taxminga ega algoritm tezroq bajariladi. 1. C doimiy 2. log (log (N)) 3. log (N) 4. N ^ C, 8. C ^ N, C> 1 9. N!
Agar murakkablik tenglamasi ushbu funktsiyalarning bir nechtasini o'z ichiga olgan algoritmning murakkabligini baholashni istasak, tenglamani jadvalda joylashgan funktsiyaga kamaytirish mumkin. Masalan, O (log (N) + N!) = O (N!). Agar algoritm kam miqdordagi ma'lumotlarga kamdan-kam hollarda chaqirilsa, O (N ^ 2) murakkabligini maqbul deb hisoblash mumkin, ammo agar algoritm real vaqtda ishlayotgan bo'lsa, O (N) ishlash har doim ham etarli bo'lmaydi. Odatda, N * log (N) murakkablikdagi algoritmlar yaxshi tezlikda ishlaydi. N ^ C murakkablikdagi algoritmlardan faqat S ning kichik qiymatlari uchun foydalanish mumkin, ularning tartibi C ^ N va N funktsiyalari bilan belgilanadigan algoritmlarning hisoblash murakkabligi! juda katta, shuning uchun bunday algoritmlardan faqat oz miqdordagi ma'lumotlarni qayta ishlash uchun foydalanish mumkin.
Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti. Bitta masalani echishning turli xil algoritmlarini ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, hisoblashning qaysi modelidan foydalanilganligi to'g'risida kelishib olishimiz kerak. Ushbu ta'lim, bir model sifatida, eng qismi uchun, biz oddiy bir protsessor foydalanish tasodifiy kirish mashinasi ( tasodifiy - kirish mashinasi, RAM operatsiyalar parallel ijro uchun taqdim emas). Ishlash vaqti ( ish vaqti ) algoritmi ostida biz bajaradigan elementar qadamlar sonini anglatadi.
Aytaylik, psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab etiladi (agar ba'zi bir xatti-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 o'z ichiga olgan) va uning bajarilishini ( bajarilishini ) uzoq vaqt davomida ajratib turishingiz kerak.
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, 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 murakkabligi tipik birliklaridan foydalanishga imkon bermaydi (soniya, millisekundlar va boshqalar), chunki agar siz turli xil dasturchilar (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. Bu, odatda, bir algoritm vaqti murakkabligi tartibini deb aytiladi T ( n hajmi kirish ma'lumotlari asosida) n. Amaliyotda T ( n ) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun asimptotik munosabatlarga murojaat qiling
Insertion-Sort protsedurasining umumiy bajarilish vaqtini hisoblash uchun biz uning narxini (operatsiyalar sonini) va ushbu satr har bir satrning yonida necha marta bajarilishini belgilaymiz. 2 dan n gacha bo'lgan har bir j uchun (bu erda n = uzunlik [ A ] - massiv o'lchami), 5 qatori necha marta bajarilishini hisoblash kerak, bu sonni t j bilan belgilaymiz. Davr ichidagi chiziqlar tekshiruvdan bir marta kam bajariladi, chunki oxirgi tekshirish pastadirdan chiqadi. Satr qiymati c takrorlangan t marta hissa beradi c m operatsiyalar umumiy sonida (ammo, bu ibora ishlatilgan xotira hajmini hisoblash uchun ishlatilishi mumkin emas).
Jarayonning ishlash vaqti nafaqat n ga bog'liq, balki kirishning kirish qismida n o'lchamining qaysi qatori bilan ta'minlanganligiga ham bog'liq. Insertion-Sort protsedurasi uchun massiv allaqachon tartiblangan bo'lsa, eng maqbul holat. So'ngra line davr birinchi tekshirish keyin 5 tugaydi (buyon A [ i ] ≤ asosiy uchun i = j - 1), shuning uchun hamma narsani t j umumiy vaqti 1, va Shunday qilib, eng qulay holatda, vaqt t ( n ), hajmi bir qator saralash uchun zarur n, bir chiziqli funksiya (bo'lgan chiziqli funktsiyasi ) tomonidan n , masalan a va b ba'zi turg'unliklar uchun T ( n ) = a n + b shakli mavjud. Ushbu Sobit tanlangan qiymatlari orqali aniqlanadi bilan 1,..., bilan 8. Agar qator teskari (pasayish) tartibda joylashgan bo'lsa, ish vaqti protsedura maksimal bo'ladi: A [ j ] har bir elementni A [1],..., A [ j - 1] barcha elementlar bilan taqqoslash kerak. Bundan tashqari, t j = j. Chunki biz eng yomon holatda protsedura vaqti ekanligini tushunamiz.
Bunday holda, T ( n ) - kvadrat ( kvadratik funktsiya ), ya'ni. shakli mavjud T ( n ) = a n 2 + b n + s. A, b va c konstantalari bu erda c 1,..., c 8 qiymatlari bilan ham belgilanadi. Bu, odatda, bir algoritm vaqti murakkabligi tartibini deb aytiladi T ( n hajmi kirish ma'lumotlarining) n. Amaliyotda T ( n ) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun, ular yordamida asimptotik munosabatlar murojaat O -symbolics. Masalan, agar algoritm ishlashi uchun talab qilinadigan tadbirlar (harakatlar) soni 16 n 2 + 12 n log n + 2 n + 3 bilan ifodalangan bo'lsa, u holda algoritm T ( n ) ning O ( n 2 ) tartibida bo'lishini anglatadi. )
Asimptotik Omatikani shakllantirishda, barcha asl ifoda shartlari katta n uchun eng katta hissa qo'shadigan narsa bilan qoldiriladi (qolgan atamalar e'tiborsiz qoldirilishi mumkin) va uning oldidagi koeffitsient e'tiborga olinmaydi (chunki barcha asimptotik baholar doimiygacha berilgan). Belgilangan O () ishlatilganda, ular aniq bajarilish vaqtini anglatmaydi, balki faqat uning yuqori chegarasi, doimiy omilgacha. Masalan, algoritm O ( n 2 ) tartibining vaqtini talab qiladi deb aytganda, ular vazifaning bajarilish vaqti elementlar sonining kvadratidan tezroq o'smasligini anglatadi.
Agar murakkablik tenglamasi ushbu funktsiyalarning bir nechtasini o'z ichiga olgan algoritmning murakkabligini baholashni istasak, tenglamani jadvalda joylashgan funktsiyaga kamaytirish mumkin. Masalan, O (log (N) + N!) = O (N!). Agar algoritm kam miqdordagi ma'lumotlarga kamdan-kam hollarda chaqirilsa, O (N ^ 2) murakkabligini maqbul deb hisoblash mumkin, ammo agar algoritm real vaqtda ishlayotgan bo'lsa, O (N) ishlash har doim ham etarli bo'lmaydi. Odatda, N * log (N) murakkablikdagi algoritmlar yaxshi tezlikda ishlaydi. N ^ C murakkablikdagi algoritmlardan faqat S ning kichik qiymatlari uchun foydalanish mumkin, ularning tartibi C ^ N va N funktsiyalari bilan belgilanadigan algoritmlarning hisoblash murakkabligi! juda katta, shuning uchun bunday algoritmlardan faqat oz miqdordagi ma'lumotlarni qayta ishlash uchun foydalanish mumkin.
Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti. Bitta masalani echishning turli xil algoritmlarini ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, hisoblashning qaysi modelidan foydalanilganligi to'g'risida kelishib olishimiz kerak. Ushbu ta'lim, bir model sifatida, eng qismi uchun, biz oddiy bir protsessor foydalanish tasodifiy kirish mashinasi ( tasodifiy - kirish mashinasi, RAM operatsiyalar parallel ijro uchun taqdim emas). Ishlash vaqti ( ish vaqti ) algoritmi ostida biz bajaradigan elementar qadamlar sonini anglatadi. Aytaylik, psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab etiladi (agar ba'zi bir xatti-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 o'z ichiga olgan) va uning bajarilishini ( bajarilishini ) uzoq vaqt davomida ajratib turishingiz kerak.
Etiboringiz uchun raxmat
