|
Urganch filiali kompyuter injiniringi fakulteti 963-21 Klo’ guruh talabasining
|
| bet | 1/23 | | Sana | 22.05.2024 | | Hajmi | 156,65 Kb. | | #249660 | | Turi | Referat |
Bog'liq Alisher Asanov Algoritmlarni loyihalash fanindan Referat
O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALARI VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
URGANCH FILIALI
KOMPYUTER INJINIRINGI FAKULTETI
963-21 Klo’ GURUH TALABASINING
REFERAT
Mavzu: Algoritmlarni vaqt va xajm murakkabligini baholashda tekis va logorifmik solishtirma mezonlar.
Bajardi: Asanov. A
Qabul qildi: Yusupova. J
URGANCH -2024
Reja:
Kirish.
Algoritm murakkabligini statik va dinamik o’lchovlari. Vaqt va xotira hajimi bo’yicha qiyinchiliklar.
Algoritmlarni eng yomon va o’rtacha xolatlarda baholash.
Algoritmlarni vaqt va hajmiy marakkabligini baholashda tekis va logorifmik solishtirma mezonlari.
Xulosa.
Foydalanilgan adabiyotlar
Kirish.
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.
|
| |
