|
4. Vaqtinchalik murakkablikni hisoblash va umumiy murakkablikni baholash funksiyalari.
Xotira doimiy ravishda arzonlashib borayotganligi va kompyuterlarning tezligi asta-sekin o'sib borishi sababli, asosiy e'tibor T vaqt murakkabligi - bu algoritmga muvofiq ishlaydigan dasturning bajarilish vaqti hisoblanadi.
Qoida tariqasida, T qiymati dastlabki ma'lumotlarning hajmiga sezilarli darajada bog'liq bo'ladi: 10 ta element ro'yxatidagi qidiruv 10 000 ta element ro'yxatiga qaraganda ancha tezroq tugaydi. Shuning uchun algoritmning murakkabligi odatda kirish ma'lumotlarining hajmi n bilan bog'liq va T (n) funktsiyasi sifatida aniqlanadi. Masalan, massivlarni qayta ishlash algoritmlari uchun massivning uzunligi n kattaligi sifatida ishlatiladi. T (n) funktsiyasi algoritmning vaqt murakkabligi deyiladi.
Aytaylik, har xil murakkablikka ega bo'lgan bir nechta algoritmlarni tanlash kerak. Qaysi biri yaxshiroq (tezroq ishlaydi)? Ma'lum bo'lishicha, bu qayta ishlash uchun ma'lumotlar massivining hajmini bilishni talab qiladi. Masalan, murakkabligi T1 (n) = 10,000 10 n, T2 (n) = 100 ⋅ n2 va T3 (n) = n3 bo'lgan uchta algoritmni taqqoslaylik.
Keling, ushbu bog'liqliklarni grafik asosida tuzamiz. N-100 uchun biz T3 (n) T2 (n)> T1 (n) mavjud ).
n ga bog'liqliklar grafigi
Algoritmik tilda dasturda e'lon qilinishi mumkin bo'lgan n uzunlikdagi A massivi bilan har xil operatsiyalarni bajarish algoritmlarini ko'rib chiqing.
int A [1: n]
Misol 1. Massivning dastlabki uchta elementlari yig'indisini hisoblang (n-3 uchun).
Ushbu muammoning echimi faqat bitta operatorni o'z ichiga oladi:
S = A [1] + A [2] + A [3]
Ushbu algoritm ikkita qo'shish operatsiyasini va xotiraga qiymat yozishning bitta operatsiyasini o'z ichiga oladi, shuning uchun uning vaqt murakkabligi T (n) = 3 massivning o'lchamiga umuman bog'liq emas.
Misol 2. Barcha massiv elementlari yig'indisini hisoblang.
Ushbu vazifani loopsiz bajarish mumkin emas:
S = A [1]
Men uchun 2 dan n gacha
NTlar
S = S + A [i]
CC
Bu yerda n - 1 ta operatsiya va xotiraga yozishning n ta amallari bajariladi, shuning uchun uning murakkabligi T (n) = 2n - 1 massivning uzunligi oshgan sari chiziqli ravishda ortib boradi.
Misol 3. A [NxN] matritsasi uchun har bir satrda maksimal elementni topadigan kodni ko'rib chiqing.
I uchun 1 dan n gacha
NTlar
max = A [i, 1];
J uchun 1 dan n gacha
NTlar
IF A [i, j]> max UNDA
max = A [i, j]
CC
CC
Ushbu algoritmda i o'zgaruvchisi 1 dan n ga o'zgaradi. Har safar i o'zgarganda, j ham 1 dan n gacha o'zgaradi. Har bir tashqi tsiklning takrorlanishi davomida ichki tsikl ham n marta bajariladi. Ichki tsiklning takrorlanishlarining umumiy soni n * n. Bu T (n) = n2 algoritmining vaqt murakkabligini aniqlaydi.
Algoritmlarni taqqoslashda ularning asimptotik murakkabligi, ya'ni n ning katta qiymatlari uchun operatsiyalar sonining o'sish tezligi qo'llaniladi.
Algoritm ba'zi bir n dan boshlab T (n) ≤ c ⋅ f (n) shart bajariladigan c doimiy bo'lsa, O (f (n)) asimptotik murakkablikka ega.
Demak, c ⋅ f (n) funktsiya grafigi T (n) funktsiya grafigidan yuqori, hech bo'lmaganda n ≥ n0 ga ko'tariladi.
Algoritm murakkablikka ega O (f (n)) (murakkablik tartibi f (n)), agar kirish ma'lumotlarining hajmi kattalashishi bilan algoritmning bajarilish vaqti f (n) funktsiyasi bilan bir xil tezlikda o'ssa.
Asimptotik murakkablik
Murakkablikni hisoblashda ko'pincha ishlatiladigan f (n) funktsiyalarini sanab o'tamiz. Funksiyalar murakkabligi oshib borishi tartibida keltirilgan. Ushbu ro'yxatdagi funktsiya qanchalik baland bo'lsa, bunday taxmin bilan algoritm tezroq bajariladi.
1.C doimiydir
2. log (log (n))
3. log (n)
4. n ^ C, 0
5.n
6.n * log (n)
7. n ^ C, C> 1
8. C ^ n, C> 1
9.n!
1. O (C) - doimiy murakkablik algoritmi. Dasturdagi aksariyat operatsiyalar faqat bir marta yoki bir necha marta bajariladi. Ma'lumotlar hajmidan qat'i nazar, har doim bir xil vaqtni talab qiladigan har qanday algoritm doimiy murakkablikka ega.
2. O (n) - bu chiziqli murakkablikning algoritmi, ya'ni ma'lumotlar hajmi 10 barobar ko'payganda, hisoblash hajmi ham taxminan 10 baravar ko'payadi. Bunday algoritmlar ma'lumotlarni o'qish va xotirada saqlash uchun bajariladi. Dasturning ishlash vaqti chiziqli bo'lib, unda kiritilgan ma'lumotlarning har bir elementi faqat chiziqli marta qayta ishlashga to'g'ri keladi.
3. Log (n)) va n * log (n) haqida - logaritmik murakkablik algoritmi. Dasturning ishlash vaqti logaritmik bo'lsa, n kattalashganda dastur ancha sekin ishlay boshlaydi. Bunday ishlash vaqtlari odatda katta muammoni kichiklarga ajratadigan va ularni alohida hal qiladigan dasturlarda uchraydi.
4. O (n2) - kvadratik murakkablik algoritmi, ya'ni ma'lumotlar hajmi 10 barobar oshganda, operatsiyalar soni (va bajarish vaqti) taxminan 100 baravar ko'payadi. To'g'ridan-to'g'ri tanlovni saralash algoritmi O (n2) kvadratik murakkablikka ega, chunki har qanday massivni saralashda ushbu algoritm (n2 - n) / 2 taqqoslash operatsiyalarini bajaradi (bu holda almashtirish operatsiyalari umuman bo'lmasligi mumkin, masalan, buyurtma qilingan qator bilan).
5. O (n3) - kubik murakkabligi algoritmi. N ning katta qiymatlari uchun murakkabligi kubikli algoritm O (n2) murakkablikka ega algoritmga qaraganda ko'proq hisoblashni talab qiladi, bu esa o'z navbatida chiziqli murakkablikka ega algoritmga qaraganda ko'proq vaqt talab etadi. N x n o'lchamdagi matritsalar (jadvallar) uchun ko'paytirish algoritmining murakkabligi O (n3) dir, chunki hosil bo'lgan matritsaning har bir elementiga n ko'paytma va n-1 qo'shimchalar kerak bo'ladi va bu elementlarning barchasi n2 ga teng.
6. O (2n) - eksponent (polinom) murakkablikning algoritmi. Bunday algoritmlar ko'pincha qo'pol kuch deb nomlangan yondashuvdan kelib chiqadi.
7. O (n!) - murakkablik algoritmi. Ular ko'pincha optimallashtirish muammolarida uchraydi, ularni faqat to'liq izlash bilan hal qilish mumkin. Ushbu turdagi eng mashxur muammo bu sayohat qilgan sotuvchi (adashgan savdogar) muammosi bo'lib, u ko'rsatilgan shaharlarning har biriga bir marta tashrif buyurib, boshlang'ich nuqtaga qaytishi kerak. Uning uchun siz sayohat narxi (yoki sayohatning umumiy uzunligi) minimal bo'ladigan maqbul marshrutni tanlashingiz kerak.
Ma'lumotlar hajmi cheklangan bo'lsa, masalan, C ning kichik qiymatlari uchun nC murakkabligi bo'lgan algoritmlardan foydalaniladi, masalan n2. Tartibi Cn va n funksiyalari bilan aniqlanadigan algoritmlarning hisoblash murakkabligi! juda katta, shuning uchun bu algoritmlar juda kichik hajmdagi muammolarni hal qilish uchungina mos keladi
Do'stlaringiz bilan baham: | 
