|
Algoritmlar murakkabligining oʻsish tartibi
|
| bet | 5/9 | | Sana | 16.12.2023 | | Hajmi | 95,51 Kb. | | #120374 |
Bog'liq 1-mavzuAlgoritmlar murakkabligining oʻsish tartibi. Murakkablikning oʻsish tartibi (yoki aksiomatik murakkablik) katta kirish hajmi uchun algoritmning murakkablik funksiyasining taxminiy xatti-harakatini tavsiflaydi. Bundan kelib chiqadiki, vaqt murakkabligini baholashda elementar amallarni koʻrib chiqishning hojati yoʻq, algoritm qadamlarini koʻrib chiqish kifoya.
Algoritm qadami – bu ketma-ket joylashtirilgan elementar amallar toʻplami, uning bajarilish vaqti kirish qadamiga bogʻliq emas, ya‘ni yuqoridan qandaydir doimiy bilan chegaralangan.
Asimptotik baholashning koʻrinishlari. F(n)>0 murakkabligini, bir xil tartibdagi g(n)>0 funksiyasini, kirish n>0 oʻlchamini koʻrib chiqaylik. Agar f(n) = O (g(n)) va n> n0 uchun c>0, n0> 0 konstantalar mavjud boʻlsa, u holda 0
Bu holda g(n) funksiyasi f(n) uchun asimptotik-aniq baho hisoblanadi. Agar f(n) algoritmning murakkablik funksiyasi boʻlsa, unda murakkablik tartibi f(n) uchun - O(g(n)) deb belgilanadi. Ushbu ibora doimiy koeffitsiyentgacha g(n) dan tez oʻsmaydigan funksiyalar sinfini belgilaydi.
Algoritmlar samaradorligini hisoblash. Algoritmlar samaradorligini hisoblashda kirish ma’lumotini qanday tanlash ko’rilayotgan algoritmni bajarilishiga yaxshigina ta’sir ko’rsatadi. Masalan, agar kirish ma’lumotlari allaqachon saralangan bo‘lsa, ba’zi saralash algoritmlari juda yaxshi ishlaydi, ayrimlari ancha past samaradorlik bilan ishlashi mumkin. Agar kirish ma’lumotlari saralanmagan, tartibsiz bo’lsa, buni aksi bo’lishi mumkin. Shuni e’tiborga olgan holda, algoritmlar tahlil qilinishi kerak.
Bunda kirish ma’lumotlari algoritm tez bajarilishi uchun qulay ko’rinishda bo‘ladi, ya’ni algoritm kam sonli amallar bilan bajariladi va kam vaqt talab qiladi. Misol uchun, agar tuzimadan qidirayotgan element tuzilmaning birinchi elementi bo’lib hisoblansa, uni qidirishga eng kam vaqt sarflanadi. Chunki tuzilmaning uzunligidan qat’iy nazar bitta solishtirish yetarli. Algoritmlarni eng yaxshi holatlarini tahlil qilishda odatda, bajarilish vaqti konstanta 1 ga teng bo‘lishi sababli ko’pincha tahlillarda bu vaziyat ko’rilmaydi.
|
| |
