|
Toshkent axborot texnologiyalri universiteti algoritmlarni loyihalash
|
| bet | 4/6 | | Sana | 05.03.2024 | | Hajmi | 131.97 Kb. | | #167339 |
Bog'liq Axmedov A. Коррупция, React 50 вопросов на собеседование, Linkedin, Маърузалар матни, 1 ON savollari, irregular VERBS, 3.Pul oqimlari to’g’risidagi hisobot, Toshkent davlat iqtisodiyot universiteti, 7-Mavzu obligatsiyalar bozori reja, «tasdiqlangan», Дизайн без названия, 7-Mavzu obligatsiyalar bozori reja (1), WEB yakuniy pdflar (3), 4-amaliy ish mavzu Risklarni baholash usullari. Riskni “Nosozli, Topografik chizmachilik. Murodov Sh. Ismatullayev RXotira 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, biz shunchaki 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 bajarilish tezligi va iste'mol qilinadigan xotira nuqtai nazaridan baholanadi. Vaqtinchalik murakkablikka e'tiborni qaratamiz, ammo shunga qaramay, biz iste'mol qilingan xotiraning hajmini aniq belgilaymiz.
Buyurtmani baholash
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.
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 qismdan 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.
|
| |
