Algoritmlarning murakkabligini baholash

Algoritmlarning murakkabligini baholash
Algoritmlar
*
Qum qutisidan
Kirish

Har qanday dasturchi uchun algoritm nazariyasi asoslarini bilish muhimdir, chunki bu algoritmlarning umumiy xususiyatlarini va ularning taqdimotining rasmiy modellarini o'rganadigan fan. Kompyuter fanlari darslaridan boshlab, biz oqim sxemasini tuzishga o'rgatiladi, bu esa keyinchalik maktabga qaraganda murakkab vazifalarni yozishda yordam beradi. Bundan tashqari, ma'lum bir muammoni hal qilishning deyarli har doim bir necha yo'li borligi sir emas: ba'zilari ko'p vaqt sarflashni, boshqa resurslarni sarflashni nazarda tutadi va boshqalar faqat yechim topishga yordam beradi.

Har doim, ayniqsa, vazifa sinfini hal qilish uchun algoritmlarni ishlab chiqishda, vazifaga muvofiq optimallashtirishni izlash kerak.
Bundan tashqari, algoritmning turli hajm va miqdorning boshlang'ich qiymatlari bilan qanday ishlashini, qanday resurslarni talab qilishini va yakuniy natijani chiqarish uchun qancha vaqt ketishini baholash muhimdir.
Bu algoritm nazariyasi bo'limi bilan shug'ullanadi – asimptotik algoritm tahlil nazariyasi.

Men ushbu maqolada baholashning asosiy mezonlarini ta'riflashni va eng oddiy algoritmni baholashga misol keltirishni taklif qilaman. Habrahabra'da algoritmlarni baholash usullari haqida maqola bor, lekin u asosan litsey o'quvchilariga qaratilgan. Ushbu nashr ushbu maqolaning chuqurlashishi deb hisoblanishi mumkin.

Ta'riflar

Algoritmning murakkabligining asosiy ko'rsatkichi muammoni hal qilish uchun zarur bo'lgan vaqt va kerakli xotira miqdori.
Bundan tashqari, vazifa klassi uchun murakkablikni tahlil qilganda, ma'lum miqdordagi ma'lumotlarni – kirish hajmini tavsiflovchi ma'lum bir raqam aniqlanadi.
Shunday qilib, algoritm murakkabligi – kirish hajmi vazifasi, deb xulosa qilish mumkin.
Algoritmning murakkabligi bir xil kirish hajmida farq qilishi mumkin, ammo turli xil kirish ma'lumotlari.

Eng yomon, o'rtacha yoki eng yaxshi murakkablik tushunchalari mavjud. Odatda, eng yomon holatda murakkabligi baholash.

Eng yomon holatda vaqtinchalik murakkablik-bu o'lchamdagi muammoni hal qilishda algoritm jarayonida amalga oshirilgan operatsiyalarning maksimal soniga teng bo'lgan kirish hajmining funktsiyasi.
Eng yomon holatda kapasitiv murakkablik-bu o'lchamdagi muammolarni hal qilishda apellyatsiya qilingan maksimal xotira hujayralariga teng bo'lgan kirish hajmining vazifasi.

Algoritmlar murakkabligi oshirish tartibi

Murakkabligi (yoki axiomatic murakkabligi) o'sishi tartibi kiritish katta hajmi bilan algoritm murakkabligi taxminiy xatti ta'riflaydi. Shundan kelib chiqadiki, vaqtinchalik murakkablikni baholashda asosiy operatsiyalarni hisobga olishning hojati yo'q, algoritmning bosqichlarini ko'rib chiqish kifoya.

Qadam algoritm-ketma-ket joylashgan elementar operatsiyalar majmui, amalga oshirish vaqti kirish hajmiga bog'liq emas, ya'ni, bir sobit ustiga cheklangan.

Asimptotik baholash turlari

O-eng yomon ish uchun baholash

Murakkabligini ko'rib chiqaylik f(n) > 0, shu tartibda funktsiyasi g (n) > 0, kirish hajmi n > 0.
Agar f(n) = O(g(n)) va C > 0, n0 > 0 sobit bo'lsa, u holda
0 < f(n) < c*g(n),
n > n0 uchun.

Bu holda g(n) funktsiyasi asimptotik-aniq baholash f (n). F(n) – algoritm murakkabligi vazifasi bo'lsa, murakkabligi tartibi f(n) – O(g(n)) deb belgilangan.

Bu ibora g(n) dan tezroq doimiy multiplikatorga aniqlik bilan o'sadigan funktsiyalar sinfini belgilaydi.

Asimptotik funktsiyalarning namunalari

f(n) g(n)
2n2 + 7n — 3 n2
98n*ln(n) n*ln(n)
5n + 2 n
8 1

Ō-yaxshiroq ish uchun baholash

Ta'rif eng yomon ish uchun baholashning ta'rifiga o'xshaydi, ammo
f (n) = ō(g(n)), agar
0 < c*g(n) < f(n)

Ō(g(n)) g(n) funktsiyasidan asta-sekin o'sib boradigan funktsiyalar sinfini doimiy multiplikatorga aniqlik bilan belgilaydi.

Θ - o'rtacha ish uchun baholash

Shuni ta'kidlash kerakki, bu holda n > n0 da f(n) funktsiyasi hamma joyda C1*g(n) va c2*g(n) o'rtasida joylashgan bo'lib, bu erda c doimiy multiplikator hisoblanadi.

Misol uchun, f(n) = n2 + n; g(n) = n2.

Algoritmlarning murakkabligini baholash mezonlari

Yagona vazn mezon (RVK) algoritm har bir qadam vaqt birligida amalga oshiriladi, deb taklif qiladi, va bir birlik hajmi uchun xotira hujayra (doimiy aniqlik bilan).
Logaritmik vazn mezonlari (LVC) xotira hujayrasida saqlanadigan operatsiya va qiymat bilan ishlov berilgan operand hajmini hisobga oladi.

LVK uchun vaqtinchalik murakkablik l(Op) qiymati bilan belgilanadi, bu erda Op operandning qiymati hisoblanadi.

LVK uchun kapasitiv murakkablik l(M) qiymati bilan belgilanadi, bu erda m xotira xujayrasining qiymati hisoblanadi.

Faktoriyani hisoblashda murakkablikni baholash misoli

Faktorial hisoblash algoritmining murakkabligini tahlil qilish kerak. Buning uchun, bu vazifa bilan psevdokode tilida yozish:
void main() {
int result = 1;
int i;
const n = ...;
for (i = 2; i <= n; i++)
result = result * n;
}

Yagona vazn mezonlari bilan vaqtinchalik qiyinchilik

Ushbu muammoning kirish hajmi n ekanligini aniqlash kifoya.
Qadamlar soni (n — 1).

Shunday qilib, RVKDAGI vaqtinchalik murakkablik o(n) ga teng.

Logaritmik vazn mezonlari bilan vaqtinchalik qiyinchilik

Ushbu nuqtada baholash kerak bo'lgan operatsiyalarni tanlash kerak. Birinchidan, bu taqqoslash operatsiyalari. Ikkinchidan, o'zgaruvchilar o'zgarishlar operatsiyalari (qo'shimcha, ko'paytirish). Tayinlash operatsiyalari hisobga olinmaydi, chunki u darhol sodir bo'lishi kerak.

Shunday qilib, bu vazifada uchta operatsiya ajratilgan:
1) i <= n

Birinchi bosqichda siz log(n) ni olasiz.

Qadamlar (n-1) beri, bu operatsiya murakkabligi bo'ladi (n-1)*log(n).
2) i = i + 1

Birinchi bosqichda siz log(i) ni olasiz.

Shunday qilib, bu miqdor olinadi .
3) result = result * i

I-bosqichda siz log((i-1) ni olasiz!).

Shunday qilib, bu miqdor olinadi .

Agar siz olingan barcha qiymatlarni qo'shsangiz va n-ni oshirish bilan asta-sekin o'sib boradigan shartlarni bekor qilsangiz, biz yakuniy ifodani olamiz .

Yagona vazn mezonlari bilan kapasitif murakkabligi

Bu erda hamma narsa oddiy. O'zgaruvchilar sonini hisoblash kerak. Vazifa tillo ishlatiladi bo'lsa, o'zgaruvchan qator har bir hujayra hisoblanadi.

O'zgaruvchilar soni kirish hajmiga bog'liq emas, chunki, murakkabligi O teng bo'ladi (1).

Logaritmik vazn mezonlari uchun kapasitiv murakkablik

Bunday holda, xotira xonasida bo'lishi mumkin bo'lgan maksimal qiymatni hisobga olish kerak. Agar qiymat aniqlanmagan bo'lsa (masalan, i > 10 operandida), Vmax ning cheklangan qiymati bor deb hisoblashadi.
Ushbu vazifada o'zgarmaydigan, qiymati n (i) dan oshmagan va qiymati n dan oshmagan o'zgarmaydigan o'zgaruvchi mavjud! (result). Shunday qilib, baholash O (log (n!)).

Natijalar

Algoritmlarning murakkabligini o'rganish juda qiziqarli vazifadir. Hozirgi vaqtda eng oddiy algoritmlarni tahlil qilish it sohasidagi kompyuter fanlari va amaliy matematika bilan shug'ullanadigan texnik mutaxassisliklar (aniq, umumiy "Informatika va hisoblash texnikasi" yo'nalishi) o'quv rejalariga kiritilgan.
Murakkablik asosida turli vazifalar sinflari ajratiladi: P, NP, NPC. Ammo bu algoritmlarni asimptotik tahlil qilish nazariyasi muammosi emas.
Tags: algoritm nazariyasi algoritmlarni baholashalgoritmyasimptotik algoritmlarni tahlil qilish
Hublar: Algoritmlar
Algoritmlarning murakkabligini baholash Mundarija kirish . Algoritm tushunchasi va uning murakkabligi choralari . Algoritmlarning vaqtinchalik va kapasitiv murakkabligi . Algoritmlarning murakkabligi bo'yicha yuqori va o'rtacha ballar . Murakkablikni tahlil qilishning asosiy usullari va usullari . Recursiv algoritmlarning murakkabligini tahlil qilish . Algoritmlarni optimallashtirish xulosa foydalanilgan adabiyotlar ro'yxati kirish an'anaviy ravishda dasturlashda algoritm murakkabligi tushunchasi kompyuter resurslaridan foydalanish bilan bog'liq: dasturni amalga oshirish uchun qancha protsessor vaqti talab qilinadi, mashinaning xotirasi qancha sarflanadi? Xotira hisobi odatda ma'lumotlar miqdori bo'yicha saqlanadi va dastur buyruqlarini yozish uchun sarflanadigan xotira hisobga olinmaydi. Vaqt nisbiy birliklarda hisoblab chiqiladi, shuning uchun bu baholash, iloji bo'lsa, turli xil soat tezligi va arxitekturada kichik farqlar bilan mashinalar uchun bir xil bo'ladi. Ushbu yondashuv tarixiy jihatdan rivojlangan va birinchi navbatda algoritm nazariyasining ilmiy va muhandislik ilovalariga yo'naltirilgan: ma'lumotlar hajmi dasturning hajmidan sezilarli darajada oshib boradi va dastur bir necha soat davomida bajarilishi mumkin. Agar ilmiy va muhandislik dasturlarida katta hisoblash vaqti foydalanuvchilarga noqulaylik tug'dirsa, unda boshqa bir qator sohalarda resurslar juda muhimdir, chunki dasturning samarasiz ishlashi tufayli butun loyihaning maqsadga muvofiqligi muammosi bo'lishi mumkin. Bu sohalarda Real vaqt tizimlari (Real-Time tizimlari) o'z ichiga oladi. Ular haqiqiy dunyo jarayonlarini boshqaradigan yoki tezkor qaror qabul qilish uchun xizmat qiluvchi axborotni qayta ishlovchi kompyuterlarga asoslangan tizimlardir. Vaqtinchalik va kapasitif - bu ish batafsil algoritmlar murakkabligi ikki xususiyatlarini muhokama qiladi. Lekin biz algoritm matnining murakkabligini (uzunligini) muhokama qilmaymiz, chunki u ijrochini (mashinani), uning tilini emas, balki muammoni hal qilish usulini tavsiflaydi. Bundan tashqari, algoritmni ishlab chiqishning mantiqiy murakkabligini muhokama qilmaymiz - dasturni yaratish uchun qancha odam-oy sarflash kerak, chunki ob'ektiv miqdoriy xususiyatlarni berish mumkin emas. Ushbu mavzularning ikkalasi ham "dasturlash texnologiyasi" (software engineering) deb nomlangan kompyuter fanlari sohasiga tegishli. 1. Algoritm tushunchasi va uning faoliyatining barcha sohalarida, xususan, axborotni qayta ishlash sohasida uning murakkabligi choralari, inson turli usullar yoki muammolarni hal qilish usullari bilan duch keladi. Ba'zi qo'shimcha talablar algoritmning norasmiy ta'rifiga olib keladi: 1.1 ta'rifi: algoritm muayyan tilda berilgan yakuniy retsept bo'lib, mumkin bo'lgan dastlabki ma'lumotlar klassi uchun umumiy bo'lgan muammoni hal qilish uchun bajariladigan elementar operatsiyalarning yakuniy ketma-ketligini belgilaydi. D - muammoning dastlabki ma'lumotlarining maydoni (majmui) va R - ko'plab mumkin bo'lgan natijalar, keyin algoritm D → R ni aks ettiradi, deb aytishimiz mumkin. chunki bunday xaritalash to'liq bo'lmasligi mumkin, quyidagi tushunchalar kiritiladi: algoritm qisman algoritm deb ataladi, agar biz natijani faqat ba'zi D D D va to'liq algoritm, agar algoritm barcha D D. D uchun to'g'ri natijaga erishsa. Algoritmlar nazariyasida algoritmning turli xil rasmiy ta'riflari joriy etildi va ajoyib ilmiy natijalar ushbu rasmiy ta'riflarning tengligi ma'nosida ekvivalentligini isbotlashdir. Algoritmning og'zaki ta'rifi variantlari rus olimi A. N. Kolmogorov va AA Markovga (9, p. 24) tegishli: 1 ta'rifi. (Kolmogorov): algoritm aniq belgilangan qoidalarga muvofiq amalga oshiriladigan har qanday hisob - kitob tizimi bo'lib, u bir necha qadamdan keyin aniq vazifani hal qilishga olib keladi. 2 ta'rifi( belgilar): algoritm - turli xil dastlabki ma'lumotlardan istalgan natijaga qadar bo'lgan hisoblash jarayonini aniqlaydigan aniq ko'rsatma. Algoritmning turli ta'riflari, aniq yoki yopiq shaklda, quyidagi talablar ketma-ketligini bildiradi (qarang: 5, p. 62-63): - algoritm boshlang'ich bajarilishi mumkin bo'lgan retseptlarning yakuniy sonini o'z ichiga olishi kerak, ya'ni. yozuvning ekstremitasining talabini qondirish ; - algoritm muammoni hal qilishda oxirgi qadamlarni bajarishi kerak, ya'ni. harakatlarning ekstremal talablarini qondirish; - algoritm barcha ruxsat etilgan dastlabki ma'lumotlar uchun yagona bo'lishi kerak, ya'ni. universallik talabini qondirish; - algoritm vazifaga nisbatan to'g'ri echimga olib kelishi kerak, ya'ni. to'g'ri talabni qondirish. Algoritm kontseptsiyasining boshqa rasmiy ta'riflari maxsus matematik konstruktsiyalarni joriy etish bilan bog'liq (post mashinasi, turing mashinasi, chizg'ichning takrorlanadigan hisoblash funktsiyalari) va bunday formalizmning ekvivalentligi va "algoritm" tushunchasi (9, p.25-27) haqidagi tezisni ifodalash. Umumiy muammoni hal qilish-biz umumiy muammo, to'g'ri va final algoritmlar, t. E. 1 berish algoritmlar uchun qo'llaniladigan ro'za ta'riflarni rioya, kelajakda ko'rib chiqamiz. Rasmiy tizim sifatida biz mavhum mashinani ko'rib chiqamiz, shu jumladan fon - Neumann arxitekturasi bilan protsessor, manzil xotirasini qo'llab-quvvatlaydi va yuqori darajadagi til bilan bog'liq "elementar" operatsiyalar to'plami. Keyinchalik tahlil qilish uchun quyidagi taxminlarni qabul qilamiz: - har bir jamoa belgilangan vaqtdan ortiq emas; - algoritmning dastlabki ma'lumotlari har birining b bitlari uchun mashina so'zlari bilan ifodalanadi. Muayyan muammo xotira so'zlari bilan belgilanadi, shuning uchun algoritm kirishida-Nb = n * b bit ma'lumoti. Umumiy muammoni hal qilish uchun algoritmni amalga oshiruvchi dastur BM bitlari uchun m mashina ko'rsatmalaridan iborat - Mb = M*b m bit ma'lumot. Bundan tashqari, algoritm mavhum mashinaning quyidagi qo'shimcha resurslarini talab qilishi mumkin:D - oraliq natijalarni saqlash uchun xotira;r - hisoblash jarayonini tashkil qilish uchun xotira (recursiv qo'ng'iroqlarni amalga oshirish va qaytarish uchun zarur bo'lgan xotira). Muayyan muammoni hal qilishda xotira so'zlari bilan berilgan N algoritm mavhum mashinaning yakuniy sonidan boshqa hech narsa qilmaydi, chunki faqat yakuniy algoritmlarni ko'rib chiqish shartlari. 3 ta'rifi (2, p.107). Algoritmning murakkabligi. Berilgan kirish uchun algoritmning murakkabligi ostida-Fa (N), biz ushbu rasmiy tizimda muayyan muammoni hal qilish uchun algoritm tomonidan amalga oshirilgan "elementar" operatsiyalar sonini tushunamiz. Algoritmni kompleks tahlil qilish muayyan muammolarni hal qilish uchun algoritm tomonidan talab qilinadigan rasmiy tizimning resurslarini kompleks baholash asosida amalga oshirilishi mumkin. Shubhasiz, resurslarning og'irligini qo'llashning turli sohalari uchun turli xil bo'ladi, bu algoritmning quyidagi keng qamrovli baholashiga olib keladi: yA=c1 * Fa(N) + c2 * M + c3 * Sd + c4 * Sr, bu erda ci resurslarning og'irligi. Algoritm murakkabligi batafsil tahlil har doim asosiy operatsiyalar soni bir xil uzunligi boshqa kiritish bo'yicha operatsiyalar soni bilan bir vaqtga to'g'ri keladi N uzunligi bir kirish bo'yicha algoritm tomonidan amalga oshiriladi emas, deb chiqadi. Bu ma'lum bir uzunlikdagi (6, p. 82-85) kirish ma'lumotlarida ushbu algoritmning murakkabligi xatti-harakatlarini aks ettiradigan maxsus belgilarni kiritish zarurligiga olib keladi. Rasmiy tizimda berilgan vazifaning ko'plab o'ziga xos muammolari bo'lsin. D Î da - muayyan muammoning vazifasi va |D| = N. umuman olganda, D kuchiga ega bo'lgan barcha o'ziga xos muammolarni o'z ichiga olgan da to'plamining o'z kichik to'plami mavjud: biz buni DN orqali belgilaymiz: DN = {dîn,: |D/ = n}; MDN orqali DN to'plamining kuchini bildiramiz , T.o'tish: saytda harakatlanish, qidiruv Keyinchalik, bu algoritm muhim ahamiyatga ega bo'lib, N o'lchamining turli muammolarini hal qilish, ba'zi hollarda eng ko'p operatsiyalarni amalga oshiradi va ba'zi hollarda operatsiyalarning eng kichik soni. Quyidagi belgilarni keltiramiz (6, p .77):. Fa ((N) - eng yomon holat - muayyan muammolarni hal qilish uchun algoritm A tomonidan amalga oshirilgan operatsiyalarning eng ko'p soni N: Ù(N) = max {Fa (D)} - DN bo'yicha eng yomon holat . FaÚ (N) - eng yaxshi ish - algoritm tomonidan amalga oshirilgan operatsiyalarning eng kichik soni n: Ú(N) = min {Fa (D)} - DN bo'yicha eng yaxshi ish. `Fa (N) - o'rtacha ish-muayyan muammolarni hal qilish uchun algoritm a tomonidan amalga oshirilgan operatsiyalarning o'rtacha soni n: `Fa(N) = (1 / MDN)*å {Fa (D)} - dastlabki ma'lumotlarning algoritmning mehnat zichligi funktsiyasiga ta'siri bo'yicha DN bo'yicha o'rtacha ish taklif qilinishi mumkin algoritmlarni tahlil qilish uchun amaliy ahamiyatga ega bo'lgan quyidagi tasnif: .Kantitativ-mehnatga bog'liq algoritm. (D) = Fa (|D|) = FA (N) miqdoriy bog'liq mehnat zichligi funktsiyasi bilan algoritmlarni misollar: bu algoritmlar, vazifasi faqat ma'lum bir kirish hajmiga bog'liq, va o'ziga xos qadriyatlarga bog'liq emas, deb massivlar va matritsalar bilan standart operatsiyalar uchun algoritmlar sifatida xizmat qilishi mumkin-matritsalarni ko'paytirish, matritsani vektor va boshqalar .Parametrik jihatdan qaram bo'lgan algoritmlar. Bu algoritmlar, mehnat zichligi kirish kattaligi bilan aniqlanmagan (odatda, bu guruh uchun kirish kattaligi odatda aniqlanadi) va qayta ishlangan xotira so'zlarining o'ziga xos qiymatlari: Fa (D) = Fa (d1,..., dn) = Fa (P1,...,Pm), parametrik jihatdan algoritmlarning M £ N misollari-tegishli kuch ketma-ketligini hisoblash orqali ma'lum bir aniqlik bilan standart funktsiyalarni hisoblash uchun algoritmlarga bog'liq. Shubhasiz, bunday algoritmlar, kirish ikki raqamli qiymatlari ega-argument vazifalari va aniqligi, operatsiyalar qiymati soni sezilarli darajada bog'liq amalga oshirish. . Algoritmlarning mehnat zichligi bo'yicha miqdoriy va parametrik. Biroq, ko'pgina amaliy holatlarda mehnat zichligi funktsiyasi kirish va kirish ma'lumotlarining qiymatiga bog'liq bo'lib, bu holda: (d) = Fa (||D||, P1,...,Pm) = Fa (N, P1,...,Pm) misol sifatida parametrik jihatdan qaram bo'lgan tashqi tsiklning aniqligi o'lchov bo'yicha miqdoriy jihatdan qaram bo'lgan qismni o'z ichiga olgan raqamli usullarning algoritmlari. . Buyurtma-mehnatga bog'liq algoritmlar.