Algoritmlarni loyhalash
ni qo‘sh TAKRORLANSIN 16 MARTA 1 ni qo‘sh
tải về 207.44 Kb.
|
- Điều hướng trang này:
- 1.1-rasm 1.2-rasm 1.3-rasm 1.4-rasm 1.5-rasm
- Algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq qidirish”( полн iy перебор )ga nisbatan tezroq taminlasa.
| 1 ni qo‘sh
TAKRORLANSIN 16 MARTA 1 ni qo‘sh TAMOM Endi bu algoritmning samaradorligi 17 ga, murakkabligi esa 17 emas, 3 ga teng. Askarlar va qayiq masalasi algoritmida 60 ta askarni daryodan o‘tkazish uchun 240 qadam bajariladi, algoritm matni esa 5 satrdan iborat. Bu algoritmning samaradorligi 240 ga, murakkabligi esa 5 ga teng. Baqa uchun tuzilgan “Baqa toq sondagi n ta bargli nilufarning 1 tartib raqamli bargiga tushdi. U barcha pashshalarni yeb 2 tartib raqamli barg ustiga borish algoritmini tuzing.” masalani algoritmida qadamlar sonini hisoblaymiz: son + 1 + son — 1 = (n —1):2 + (n — 1):2 = n — 1. Demak, har qanday n toq son uchun algoritmni samaradorligi n - 1 ga teng ekan. Algoritmning murakkabligi esa n toq son nechaga teng bo‘lishidan qat’iy nazar, 5 ga teng bo‘ladi! Baqa masalasiga oid algoritmlarning samaradorligi faqat n sonining qiymatiga bog‘liq. Chunki masala shartida Baqa har bir bargdagi pashshani yeb chiqishi talab qilinadi. U holda barglar soni n ta ekanligi va Baqa biror bargning ustida turgandan keyin harakat boshlanganligidan qadamlar soni doimo n-1 ta bo‘lishi kelib chiqadi. Haqiqatan, masalan, agar 1 tartib raqamli bargdan 4 tartib raqamlibargga o‘tish кегак bo‘lsa, u holda barcha imkoniyatlarni 1.1—1.2-rasmlarda, agar 1 tartib raqamli bargdan 5 tartib raqamli bargga o‘tish kerak bo‘lsa, u holda barcha imkoniyatlarni 1.3—1.5-rasmlardan ko‘rishimiz mumkin. 1.1-rasm 1.2-rasm 1.3-rasm 1.4-rasm 1.5-rasm Algoritm samaradorligi. 1.Algoritm samarali deb ataladi agar real kirish ma'lumotlari uchun u tezkor amalga oshirilsa. 2. Algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq qidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa. "To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, buning natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular ko'rib chiqilayotgan masalaning ichki tuzilishi va hisoblash qobiliyati haqida foydali ma'lumotlarni taqdim etadilar. Polinomial vaqt samaradorlik ko'rsatkichi sifatida. Tabiiy kombinatorial masalalarda qidirish vaqti, kirish ma'lumotlari N hajmiga nisbatan eksponensional o'sishga moyildir; agar o'lcham bittaga ko'paysa, unda imkoniyatlar xajmi bir necha marta ko'payadi. Bunday masalalarni yechish uchun yaxshi algoritm yanada samarali miqyoslash modeliga ega bo'lishi kerak; kirish ma'lumotlarining kattalashib borishi bilan o’zgarmas ko’paytuvchiga(aytaylik, ikki baravar) oshishi bilan algoritmning bajarilish vaqti ham qandaydir o’zgarmas S ko’paytuvchiga ko'payishi kerak. Agar algoritm polinomial bajarilish vaqtiga ega bo'lsa, u samarali deb ataladi. Lekin, polinomial vaqt d ning katta qiymatlarida yaxshi natija bermasligi mumkin, masalan d>=100 holatda bu son juda katta bo’ladi, natijada polinomial bajarilish vaqti kattalashib ketadi. Algoritm ishlayveradi. Bu xolda N^d faqat chegara vazifasini o’taydi. Algoritmning vaqti va hajmiy murakkabligi, algoritmda ishlatilgan operatsiyalar soni va ularning har birining vaqti bilan bog'liqdir. Bu yuzdan, bir algoritmning vaqti va hajmiy murakkabligini baholash uchun, odatda algoritmdagi har bir operatsiyani bajarish uchun kerak bo'lgan vaqtni hisoblash kerak. Algoritmlarni tekis solishtirish usuli, algoritmdagi har bir operatsiyani bajarish uchun kerak bo'lgan vaqtni hisoblashga asoslanadi. Bunda, algoritmni bajarish uchun kerak bo'lgan eng katta vaqtli operatsiya topiladi va bu operatsiya uchun kerak bo'lgan vaqtni hisoblash uchun o'zgaruvchilar yordamida yechiladi. Boshqa operatsiyalar esa bu o'zgaruvchilarga qo'shiladi. Bunday qilib, algoritmning umumiy vaqti topiladi. Logarifmik solishtirish usuli esa algoritmdagi har bir operatsiyani bajarish uchun kerak bo'lgan vaqtni hisoblashda logarifmik funksiyalardan foydalanadi. Bu usul, algoritmdagi operatsiyalar soni katta bo'lgan holatlarda foydali bo'ladi. Bunda, algoritmning umumiy vaqti logarifmik funksiyalar yordamida yechiladi.Bunday solishtirish usullari foydali bo'lishi uchun, algoritmlarning murakkabligi vaqti va hajmiy murakkabligi bilan bog'liq bo'lgan holatlarda qo'llaniladi. Bunday holatlarda, algoritmning murakkabligi vaqti va hajmiy murakkabligi ko'payib, algoritmni bajarish vaqtini keltirib chiqarishi mumkin. tải về 207.44 Kb. Chia sẻ với bạn bè của bạn:
|