Mavzu: Asimptotik analizga murojaat usullari. Mummolar & yechimlar

Ko'plab muammolarda uchraydigan yana bir xususiyat - bu ularning asosan diskretligi. Ko'plab muammolarda uchraydigan yana bir xususiyat-bu ularning asosiy ajralib turishi. Boshqacha qilib aytganda, bu shunday masalalarki, ularda yechim kombinatorial variantlarning keng to'plamidan qidirib topiladi; maqsad aniq belgilangan shartlarni qanoatlantiradigan echimni samarali topishdir.

Hisoblash samaradorligi tushunchasini aniqlash uchun, biz birinchi navbatda ish vaqtining samaradorligiga e'tibor qaratamiz: algoritmlar tez ishlashi kerak. Ammo algoritmlar boshqa resursrlardan foydalanish nuqtai nazaridan ham samarali bo'lishi mumkinligini tushunish muhimdir. Xususan, algoritm tomonidan ishlatilinadigan xotira miqdori ham samaradorlikning muhim jixati bo'lishi mumkin.

Algoritm samaradorligi.

(1)T: algoritm samarali deb ataladi agar real kirish ma'lumotlari uchun u tezkor amalga oshirilsa.

(2)T: 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.

A

Matematik nuqtai nazardan ushbu masshtablash modelini quyidagicha shakllantirish mumkin. Aytaylik, algoritm quyidagi xususiyatga ega: c> 0 va d> 0 absolyut konstantalar mavjudki, har qanday N xajmli kirish ma'lumotlari to'plami uchun, bajarilish vaqti cN^d sondagi eng sodda operatsiyalar soni bilan chegaralanadi. Boshqacha qilib aytganda, bajarilish vaqti N^d ga proportsionallikdan ko’p emas. Qanday bo'lmasin, ba'zi bir c va d lar uchun bajarilish vaqti ushbu chegaradan oshmaganda, algoritm polinomial bajarilish vaqtini ta'minlaydi deymiz yoki u polinomial vaqtga ega bo'lgan algoritmlar toifasiga kiradi. polinomial vaqtga ega har qanday chegara yuqoridagi masshtablashga ega bo’ladi.