|
Algoritm murakkabligini static va dinamik o’lchovlari. Vaqt va hajm bo’yicha qiyinchiliklar
|
| bet | 1/12 | | Sana | 16.03.2024 | | Hajmi | 37.9 Kb. | | #174698 |
Bog'liq Algoritm murakkabligini static va dinamik o’lchovlari. Vaqt va h-fayllar.org Mavzu, 4-Laboratoriya, Mavzu Tarmoqlararo ekran texnologiyalari Reja, MTA 1-amaliy ish topshiriqlari, netniki, parviz 1-mustaqil ish, Ismoilov 2, j.abdulaziz.dock, 3mbum, 2-, Kimlar pedagogik faoliyat bilan shug, lab1-4.t.x, 1-Mustaqil ta'lim, 7-mavzu, openstack
Algoritm murakkabligini static va dinamik o’lchovlari. Vaqt va hajm bo’yicha qiyinchiliklar
O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
"Dasturiy injiniring" kafedrasi
“Dasturlash 2” fanidan
Bajardi: KI-S21-04 -guruh talabasi
Sobirova I
Rahbar: MAXKAMOVA D.
SAMARQAND – 2023
Mavzu. Chiziqli va tarmoqlanuvchi algoritmlar.
1.
|
Algoritm murakkabligini static va dinamik o’lchovlari.
Vaqt va hajm bo’yicha qiyinchiliklar
|
2.
|
Algoritmlarni eng yomon va o’rtacha holatlarda baholash
|
3.
|
Algoritmlarni vaqt va hajmiy murakkablik bo’yicha baholashda tekis va logarifmik solishtirma mezonlar.
|
4.
|
Taqribiy integrallash usuli va aniqligi bo’yicha hisoblash
|
|
| Reja
Nazariy qism
Algoritm murakkabligini static va dinamik o’lchovlari. Vaqt va hajm bo’yicha qiyinchiliklar
Algoritmning murakkabligi vaqt va makon nuqtai nazaridan uning samaradorligining o'lchovidir. Algoritmni amalga oshirish uchun tanlashdan oldin uning murakkabligini hisobga olish kerak, chunki u dasturning ishlashiga ta'sir qilishi mumkin.
Algoritm murakkabligining statik o'lchovlari algoritmni amalda ishga tushirmasdan tahlil qilishni anglatadi. Bu ko'pincha kirish hajmiga qarab algoritm bajaradigan amallar yoki qadamlar sonini hisoblash orqali amalga oshiriladi. Bu algoritmning ishlash vaqtining yuqori chegarasini ta'minlashi mumkin va "O(n)" yoki "O(n^2)" kabi matematik belgilar yordamida ifodalanishi mumkin.
Algoritm murakkabligining dinamik o'lchovlari algoritm ishlayotgan paytda tahlil qilishni anglatadi. Bu ma'lum bir kirishda algoritmning haqiqiy ishlash vaqtini yoki xotiradan foydalanishni o'lchashni o'z ichiga olishi mumkin. Bu algoritm samaradorligini aniqroq baholashni ta'minlaydi, ammo o'lchash qiyinroq va vaqt talab qilishi mumkin.
Vaqt yoki makon samaradorligi uchun algoritmlarni optimallashtirishga urinishda qiyinchiliklar paydo bo'lishi mumkin. Ba'zi hollarda, algoritm ishlashining bir tomonini yaxshilash ikkinchisining narxiga olib kelishi mumkin. Masalan, xotirani tejaydigan ma'lumotlar strukturasidan foydalanish undagi operatsiyalarni bajarish uchun ko'proq vaqt talab qilishi mumkin. Bundan tashqari, ba'zi algoritmlar eng yomon va o'rtacha ish ko'rsatkichlari o'rtasida farqlarga ega bo'lishi mumkin, bu esa ma'lum bir vaziyat uchun eng yaxshi algoritmni tanlashni qiyinlashtirishi mumkin. Algoritmlarni loyihalash va amalga oshirishda ushbu omillarni diqqat bilan ko'rib chiqish muhimdir.
Vaqt murakkabligi nuqtai nazaridan, statik o'lchov algoritmning ishlashi kirish hajmi bilan qanday o'zgarishini tasvirlash uchun ishlatiladigan katta O belgisidir. Katta O belgisi algoritmning eng yomon vaqt murakkabligining yuqori chegarasini ta'minlaydi va u odatda kirish hajmiga bog'liq holda algoritm tomonidan talab qilinadigan operatsiyalar soni bilan ifodalanadi.
Masalan, vaqt murakkabligi O(n) bo‘lgan algoritm kiritish hajmi n ga mutanosib bo‘lgan bir qancha amallarni bajarishni talab qiladi. Vaqt murakkabligi O(n^2) boʻlgan algoritm kiritish hajmining kvadratiga mutanosib boʻlgan bir qancha operatsiyalarni talab qiladi.
Hajmi nuqtai nazaridan, statik o'lchov fazoning murakkabligi bo'lib, u algoritmga kirish hajmiga qarab muammoni hal qilish uchun qancha xotira talab qilishini tavsiflash uchun ishlatiladi. Kosmik murakkablik odatda kirish hajmiga bog'liq holda algoritm tomonidan talab qilinadigan xotira miqdori bilan ifodalanadi.
Masalan, fazoviy murakkabligi O(1) bo‘lgan algoritm kiritish hajmidan qat’iy nazar, belgilangan xotira hajmini talab qiladi. Fazoviy murakkabligi O(n) bo'lgan algoritm kirish hajmiga mutanosib xotirani talab qiladi.
Biroq, statik o'lchovlar har doim ham algoritmning ishlashi haqida to'liq tasavvurni bermaydi. Ba'zi hollarda, algoritmning haqiqiy ishlashi faqat kirish hajmiga emas, balki maxsus kirish ma'lumotlariga bog'liq bo'lishi mumkin. Bunday hollarda murakkablikning dinamik o'lchovi, masalan, o'rtacha yoki eng yaxshi holat murakkabligi ko'proq mos kelishi mumkin.
|
| |
