Mavzu : Algoritm murakkabligini statik va dinamik o’lchovlari. Vaqt va xotira hajmi bo’yicha qiyinchiliklar reja

O (N) - Dasturning ishlash vaqti chiziqli odatda kirishning har bir elementi faqat chiziqli marta qayta ishlanishi kerak bo'lganda.
O (N 2), O (N 3), O (N a) - Polinom murakkabligi.
O (N 2) -kvadrat murakkablik, O (N 3) - kubik murakkablik
O (Log (N)) - Dastur qachon ishlaydi logarifmik, dastur N ortishi bilan ancha sekinroq ishlay boshlaydi. Bunday ish vaqtlari odatda katta masalani kichiklarga ajratadigan va ularni alohida yechiydigan dasturlarda uchraydi.
O (N * log (N)) - Bunday ish vaqti o'sha algoritmlarga ega katta muammoni kichikga bo'lish, va keyin ularni hal qilib, ularning echimlarini birlashtiring.
O (2 N) = Eksponensial murakkablik. Bunday algoritmlar ko'pincha qo'pol kuch deb ataladigan yondashuvdan kelib chiqadi.
Dasturchi algoritmlarni tahlil qilish va ularning murakkabligini aniqlay olishi kerak. Algoritmning vaqt murakkabligini uning boshqaruv tuzilmalarini tahlil qilish asosida hisoblash mumkin.

Loopsiz va rekursiv chaqiruvlarsiz algoritmlar doimiy murakkablikka ega. Agar rekursiya va looplar bo'lmasa, barcha boshqaruv tuzilmalari doimiy murakkablikdagi tuzilmalarga qisqartirilishi mumkin. Binobarin, butun algoritm ham doimiy murakkablik bilan tavsiflanadi.
Algoritmning murakkabligini aniqlash, asosan, tsikllar va rekursiv chaqiruvlarni tahlil qilishga qisqartiriladi.
Masalan, massiv elementlarini qayta ishlash algoritmini ko'rib chiqing.
i uchun: = 1 dan N gacha
Boshlash
...
Oxiri;
Ushbu algoritmning murakkabligi O (N), chunki sikl tanasi N marta bajariladi va sikl tanasining murakkabligi O (1) ga teng.
Agar bir sikl boshqasiga o'rnatilgan bo'lsa va ikkala tsikl ham bir xil o'zgaruvchining o'lchamiga bog'liq bo'lsa, unda butun qurilish kvadratik murakkablik bilan tavsiflanadi.
i uchun: = 1 dan N gacha
j uchun: = 1 dan N gacha
Boshlash
...
Oxiri;
Ushbu dasturning murakkabligi O (N 2).
Mavjud Algoritmning murakkabligini tahlil qilishning ikkita usuli: pastdan yuqoriga (ichki boshqaruv tuzilmalaridan tashqi tuzilmalargacha) va tushayotgan (tashqi va ichki tomondan).

O (H) = O (1) + O (1) + O (1) = O (1);
O (I) = O (N) * (O (F) + O (J)) = O (N) * O (shart dominantlari) = O (N);
O (G) = O (N) * (O (C) + O (I) + O (K)) = O (N) * (O (1) + O (N) + O (1)) = O (N 2);
O (E) = O (N) * (O (B) + O (G) + O (L)) = O (N) * O (N 2) = O (N 3);
O (D) = O (A) + O (E) = O (1) + O (N 3) = O (N 3)
Bu algoritmning murakkabligi O (N 3).
Qoida tariqasida, dasturning ishlash vaqtining taxminan 90% takrorlashni talab qiladi va faqat 10% to'g'ridan-to'g'ri hisoblanadi. Dasturlarning murakkabligini tahlil qilish shuni ko'rsatadiki, qaysi qismlar ushbu 90% ga to'g'ri keladi - bular eng katta chuqurlikdagi tsikllardir. Takrorlashlar o'rnatilgan halqalar yoki ichki rekursiya sifatida tashkil etilishi mumkin.
Ushbu ma'lumotlardan dasturchi samaraliroq dastur yaratish uchun quyidagi tarzda foydalanishi mumkin. Avvalo, takrorlashning chuqurligini kamaytirishga harakat qilishingiz mumkin. Keyin eng chuqur halqalardagi bayonotlar sonini kamaytirish haqida o'ylashingiz kerak. Agar bajarilish vaqtining 90% ichki halqalarni bajarishda bo'lsa, u holda bu kichik bo'limlarning 30% ga qisqarishi butun dasturni bajarish vaqtining 90% * 30% = 27% qisqarishiga olib keladi.
Bu eng oddiy misol.
Matematikaning alohida bo'limi algoritmlarning samaradorligini tahlil qilish bilan shug'ullanadi va eng maqbul funktsiyani topish unchalik oson emas.
Keling, baho beramiz massivdagi ikkilik qidiruv algoritmi - dixotomiya.
Algoritmning mohiyati: biz massivning o'rtasiga o'tamiz va kalitning o'rta element qiymatiga mos kelishini qidiramiz. Agar moslikni topa olmasak, biz kalitning nisbiy hajmi va median qiymatini ko'rib chiqamiz va keyin ro'yxatning pastki yoki yuqori yarmiga o'tamiz. Bu yarmida biz yana o'rtani qidiramiz va yana kalit bilan taqqoslaymiz. Agar u ishlamasa, joriy intervalni yana yarmiga bo'ling.
funktsiyani qidirish (past, yuqori, kalit: integer): butun;
var
o'rta, ma'lumotlar: butun son;
boshlash
past bo'lganda<=high do
boshlash
o'rta: = (past + yuqori) div 2;
ma'lumotlar: = a;
agar kalit = ma'lumotlar bo'lsa
qidiruv: = o'rta
boshqa
kalit bo'lsa< data then
yuqori: = o'rta-1
boshqa
past: = o'rta + 1;
oxiri;
qidiruv: = - 1;
oxiri;
Loopning birinchi iteratsiyasi butun ro'yxat bilan bog'liq. Har bir keyingi iteratsiya pastki ro'yxat hajmini yarmiga qisqartiradi. Shunday qilib, algoritm uchun ro'yxatning o'lchamlari
n n / 2 1 n / 2 2 n / 2 3 n / 2 4 ... n / 2 m
Oxirida shunday m butun soni bo'ladi
n / 2 m<2 или n<2 m+1
Chunki m n / 2 m bo'lgan birinchi butun sondir<2, то должно быть верно
n / 2 m-1> = 2 yoki 2 m =
Bundan kelib chiqadi
2 m = Tengsizlikning har bir qismining logarifmini olamiz va olamiz
m = m qiymati = bo'lgan eng katta butun sondir<х.
Shunday qilib, O (log 2 n).Odatda hal qilinayotgan muammoning tabiiy “o‘lchami” (odatda u ishlov beradigan ma’lumotlar miqdori) bo‘ladi, biz uni N deb ataymiz. Oxir oqibat, biz N o‘lchamdagi ma’lumotlarni qayta ishlash uchun dastur uchun zarur bo‘lgan vaqt uchun ifodani olishni istaymiz. funksiyasi N. Odatda bizni o'rtacha holat qiziqtirmaydi - "odatiy" kirishlar bo'yicha dasturning kutilayotgan ish vaqti, eng yomoni esa eng yomon kiritish bo'yicha dasturning kutilayotgan ish vaqti.
Ba'zi algoritmlar o'rtacha va eng yomon holatlar uchun aniq matematik formulalar ma'lum bo'lgan ma'noda yaxshi o'rganilgan. Bunday formulalar matematik xarakteristikalar bo'yicha ishlash vaqtini topish uchun dasturlarni sinchkovlik bilan o'rganish va keyin ularning matematik tahlilini o'tkazish orqali ishlab chiqiladi.
Ushbu turdagi tahlil uchun bir nechta muhim sabablar mavjud:
1. Yuqori darajadagi tilda yozilgan dasturlar mashina kodlariga tarjima qilinadi va u yoki bu operatorni bajarish uchun qancha vaqt ketishini tushunish qiyin bo'lishi mumkin.
2. Ko'pgina dasturlar kiritilgan ma'lumotlarga juda sezgir va ularning ishlashi ularga juda bog'liq bo'lishi mumkin. O'rtacha holat dastur qo'llaniladigan ma'lumotlar bilan bog'liq bo'lmagan matematik fantastika bo'lib chiqishi mumkin va eng yomon holat bo'lishi mumkin emas.
Saralashda eng yaxshi, o'rtacha va eng yomon holatlar katta rol o'ynaydi.
Saralash hisobi

O-murakkablik tahlili ko'plab amaliy dasturlarda keng tarqaldi. Shunga qaramay, uning cheklovlarini aniq tushunish kerak.
TO yondashuvning asosiy kamchiliklari quyidagilarni o'z ichiga oladi:
1) murakkab algoritmlar uchun O-baholarini olish, qoida tariqasida, juda ko'p vaqt talab qiladi yoki deyarli imkonsizdir;
2) ko'pincha "o'rtacha" murakkablikni aniqlash qiyin,
3) O-baholari algoritmlar orasidagi nozik farqlarni aks ettirish uchun juda qo'pol,
4) O-tahlil kichik hajmdagi ma'lumotlarni qayta ishlashda algoritmlarning harakatini tahlil qilish uchun juda kam ma'lumot beradi (yoki umuman bermaydi).
O-notatsiyasida murakkablikni aniqlash ahamiyatsiz emas. Xususan, ikkilik qidiruvning samaradorligi pastadirlarni joylashtirish chuqurligi bilan emas, balki har bir keyingi urinishni tanlash usuli bilan belgilanadi.
Yana bir qiyin qism - "o'rtacha holat" ni aniqlash. Algoritmning ishlash shartlarini bashorat qilishning iloji yo'qligi sababli buni qilish odatda juda qiyin. Ba'zan algoritm katta, murakkab dasturning bir qismi sifatida ishlatiladi. Ba'zan apparat va/yoki operatsion tizimning samaradorligi yoki kompilyatorning ba'zi komponentlari algoritmning murakkabligiga sezilarli ta'sir qiladi. Ko'pincha, bir xil algoritm turli xil ilovalarda ishlatilishi mumkin.
Algoritmning vaqt murakkabligini "o'rtacha" tahlil qilish bilan bog'liq qiyinchiliklar tufayli ko'pincha eng yomon va eng yaxshi holatlar uchun taxminlar bilan kifoyalanish kerak. Ushbu hisob-kitoblar asosan "o'rtacha" qiyinchilikning pastki va yuqori chegaralarini belgilaydi. Aslida, agar algoritmning murakkabligini "o'rtacha" tahlil qilishning iloji bo'lmasa, Merfi qonunlaridan biriga amal qilish kerak, unga ko'ra eng yomon holat uchun olingan baho "o'rtacha" murakkablikning yaxshi yaqinlashuvi bo'lib xizmat qilishi mumkin. ".
Ehtimol, O-funksiyalarining asosiy kamchiliklari ularning juda qo'polligidir. Agar A algoritmi qandaydir vazifani 0,001 * N s da bajarsa, uni B algoritmidan foydalangan holda hal qilish uchun 1000 * N s kerak bo'lsa, u holda B A dan million marta tezroq bo'ladi. Shunga qaramay, A va B bir xil vaqt murakkabligi O ga ega. (N).
Ushbu ma'ruzaning ko'p qismi algoritmlarning vaqt murakkabligini tahlil qilishga bag'ishlangan. Murakkablikning boshqa shakllari ham borki, ularni unutmaslik kerak: fazoviy va intellektual murakkablik.
Fazoviy murakkablik, dasturni bajarish uchun zarur bo'lgan xotira miqdori haqida avval aytib o'tilgan edi.
Algoritmning intellektual murakkabligini tahlil qilishda algoritmlarning tushunarliligi va ularni ishlab chiqishning murakkabligi tekshiriladi.
Murakkablikning barcha uchta shakli odatda o'zaro bog'liqdir. Odatda, yaxshi vaqtinchalik murakkablik hisobiga ega algoritmni ishlab chiqishda uning fazoviy va/yoki intellektual murakkabligidan voz kechish kerak. Misol uchun, tez tartiblash algoritmi namunaviy tartiblash algoritmidan sezilarli darajada tezroq. Saralash tezligini oshirish uchun to'lov saralash uchun zarur bo'lgan ko'proq xotirada ifodalanadi. Tez tartiblash uchun qo'shimcha xotiraga bo'lgan ehtiyoj bir nechta rekursiv qo'ng'iroqlar bilan bog'liq.
Quicksort, shuningdek, kiritish tartibidan ko'ra aqlliroq murakkabroq. Agar siz yuzlab odamlardan ob'ektlar ketma-ketligini saralashni so'rasangiz, ularning aksariyati namunaviy tartiblash algoritmidan foydalanadi. Ulardan birortasi ham tezkor saralashdan foydalanishi dargumon. Tez tartiblashning ko'proq intellektual va fazoviy murakkabligining sabablari aniq: algoritm rekursiv, uni tasvirlash ancha qiyin, algoritm oddiyroq tartiblash algoritmlariga qaraganda uzunroq (dastur matnini anglatadi).
Ko'pincha bir xil muammoni hal qilish uchun bir nechta algoritmlar ishlab chiqilishi mumkin. Shu munosabat bilan savol tug'iladi: algoritmlarning qaysi biri "yaxshiroq"?
Ko'pgina hollarda, "yaxshiroq", aftidan, xuddi shu kiritilgan ma'lumotlardan foydalangan holda, kamroq hisoblash resurslarini (xotira va vaqt) sarflaydigan muammoni hal qilishga keladigan algoritmdir. Bu, albatta, bo'sh fikr. Aniqroq fikr yuritish uchun biz bir nechta tushunchalarni kiritamiz.
Algoritmni hisoblash jarayoni - bu ba'zi kiritilgan ma'lumotlar uchun algoritmning bajarilishidan o'tgan bosqichlar ketma-ketligi.
Algoritmning o'zi va ushbu algoritm tomonidan yaratilgan hisoblash jarayoni o'rtasidagi farqni tushunish muhimdir. Birinchisi faqat tavsifi ikkinchi.
Algoritmning vaqt murakkabligi - ba'zi kiritilgan ma'lumotlar uchun algoritmning hisoblash jarayonini yakunlash uchun zarur bo'lgan vaqt \ (T \).
Amalga oshirish muddati aniq ijrochiga bog'liqligi aniq. Aytaylik, elektron kalkulyator va superkompyuter bir xil algoritmni turli vaqtlarda ishlatishi mumkin.
Biroq, \ (T \) vaqtni elementar harakatlar soni \ (k \) va elementar harakatning o'rtacha bajarilish vaqti \ (t \) bilan ifodalash mumkin:
Bundan tashqari, \ (k \) xususiyatdir eng algoritm, va \ (t \) - ijrochining xossasi.
Berilgan ijrochi uchun \ (t \) doimiy deb hisoblanishi mumkinligi sababli, odatda algoritmlarning murakkabligi doimiy koeffitsientgacha baholanadi. Boshqacha qilib aytganda, algoritmning murakkabligi taxmin qilinadi o'sish tartibi.
O'sish tartibi musbat aniq funksiya \ (g (x) \) o'sish tartibiga ega \ (f (x) \) (yozma \ (g (x) = \ mathcal (O) (f (x)) \)) agar \ (\ mavjud c> 0: \: \ forall x> x_0, \, g (x) \ leq c f (x) \).
Kirish ma'lumotlariga qarab, algoritm turli vaqtlarda ishlashi mumkin. Odatda baholanadi o'rtacha murakkablik va murakkablik eng yomoni... ga qaramlik ham mavjud miqdori ma'lumotlarni kiritish \ (n \). Odatda \ (n \) ning o'sish tartibi baholanadi.
Masalan, ma'lumotlarni o'qish va uni xotirada massiv sifatida saqlash murakkablikga ega bo'ladi \ (\ mathcal (O) (n) \) yoki chiziqli murakkablik, va matritsani ko'paytirish allaqachon kub\ (\ matematik (O) (n ^ 3) \).
Algoritmning vaqt murakkabligidan tashqari, u ham muhimdir fazoviy algoritmning murakkabligi.
Algoritmning fazoviy murakkabligi sondir qo'shimcha xotira \ (S \), algoritm ishlashi uchun talab qilinadi. Kirish ma'lumotlarini saqlash uchun zarur bo'lgan xotira \ (D \) \ (S \) tarkibiga kiritilmagan.
\ (S \) odatda aktuatorga ham bog'liq. Misol uchun, agar ikkita aktuator mos ravishda 4 va 8 baytli butun sonlarni qo'llab-quvvatlasa, u holda 8 baytli butun sonlar uchun algoritmning fazoviy murakkabligi 4 baytli butun sonlarga qaraganda ikki baravar katta bo'ladi. Shuning uchun fazoviy murakkablik bir xil o'sish tartibida baholanadi.