Rekursiya va Master Teoremasi. Algoritmlar va Murakkablik. 2-Qism

Ushbu maqolada Rekursiv algoritmlar va ularning ishlash vaqti analizi haqida gaplashamiz.

Bu maqolani o'qishdan oldin, 1-maqola Katta Oda keltirilgan O, Omega va Theta notationlar, umuman Time Complexity haqida o'qib, bu tushunchalarni yaxshilab o'rganishni maslahat beraman.

Rekursiya

Rekursiya deb o'zini o'zi chaqiradigan funksiyalar orqali masalani ishlash usuliga aytiladi.

Bu maqolada, rekursiya aynan qanday ishlashi haqida ortiqcha to'xtalmaymiz, agar rekursiyani bilmasangiz, avval u haqida o'rganib, bir nechta Leetcode masalalarini ishlashni maslahat beraman.

n!

Rekursiv algoritmga eng oddiy misol sonni faktorialini hisoblashni ko'rishimiz mumkin. Berilgan \(n\) soni uchun uning faktoriali \(fact(n)\) quyidagicha hisoblanadi:

\[ fact(n) = 1 \times 2 \times ... \times n = \prod_{i=1}^{n}{i} \]

Bu formulani quyidagi kabi rekursiv ko'rinishda yozish mumkin:

\[ \begin{equation} fact(n)= \begin{cases} 1, & n = 0 \text{ bo'lsa,}\ \\ n \times fact(n - 1), & \text{aks holda} \end{cases} \end{equation} \]

Ana endi, bu shu formulani dastur ko'rinishga ham keltirsak bo'ladi:

int fact(int n) {
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

Bu algoritmni ishlash vaqtini hisoblash qiyin emas. Berilgan \(n\) soni uchun fact() funksiyasi ko'pi bilan \(n\) marta chaqiriladi va har bir chaqiruvda fact()ni ichida constant miqdordagi amallar bajariladi. Demak, Time Complexityni \(O(1 \times n)\), ya'ni \(O(n)\) ko'rinishida ifodalashimiz mumkin.

Umuman olganda, odatda rekursiv algoritmlar uchun upper-bound yoki Time Complexityni hisoblash uchun, rekursiv funksiya necha marta chaqirilishi, har bir chaqiruvda ko'pi bilan nechta amal bajarilishini va ularni ko'paytmasini hisoblash yetarli.

Fibonacci

Fibonacci ketma-ketligi deb quyidagi kabi hosil qilingan ketma-ketlikka aytiladi:

\[ \renewcommand{\arraystretch}{2.5} \begin{equation} fib(n)= \begin{cases} 0, & n = 0 \text{ bo'lsa,} \\[6pt] 1, & n = 1 \text{ bo'lsa,} \\[6pt] fib(n - 1) + fib(n - 2), & \text{aks holda} \end{cases} \end{equation} \]

Buni quyidagicha kodini yozishimiz mumkin:

int fib(int n) {
   if (n == 0)
      return 0;
   else
   if (n == 1)
      return 1;
   else
     return fib(n - 1) + fib(n - 2);
}

Bu algoritmni Time Complexitysini hisoblash uchun yuqoridagi aytilgan usuldan foydalanamiz:

aytaylik fib()ga umumiy chaqiruvlar soni \(k\) bo'lsin
har bir chaqiruvda fib() ichida bajariladigan amallar soni \(m\) bo'lsin
unda Time Complexityni \(O(km)\) deyishimiz mumkin

Bu yerda \(m\) ni qiymatini \(1\) deb xulosa qilishimiz mumkin, sababi fib()ni ichida constant miqdordagi amallar bajarilmoqda.

Lekin \(k\) ni qiymatini hisoblash birozgina murakkabroq. Sababi, har bir fib() ga chaqiruvni ichida ko'pi bilan yana ikkita chaqiruv bor. \(n \leq 1\) bo'lguniga qadar, fib() ga chaqiruvlar soni ko'pi bilan ikki martaga oshib boraveradi. Bundan esa, fib()ga umumiy chaqiruvlar soni \(2^n\) bo'lishini xulosa qilishimiz mumkin.

\(O(2^n)\) ni ko'rsatishni yana bir usuli, rekursiya fib(n)=fib(n-1)+fib(n-1) bo'lganida, \(n \leq 1\) bo'lguniga qadar, fib()ga chaqiruvlar soni doim aniq ikki martaga oshardi va \(\Omega(2^n)\) ham to'g'ri bo'lardi. Bu variant yuqoridagi yechimdan ko'ra aniq ko'proq amal bajargani uchun \(O(2^n)\) to'g'ri upper-bound hisoblanadi.

Quyida \(fib(6)\) ga chaqiruvlarni daraxt ko'rinishi keltirilgan:

big_o

Ko'rib turganingizdek, chaqiruvlar soni eksponensial oshib bormoqda. Albatta, chaqiruvlar sonining aniq qiymati \(2^n\) dan kichik bo'ladi, lekin Katta O uchun upper boundning o'zi kifoya. Shuning uchun, bu algoritmni Time Complexitysini \(O(2^n)\) deyishimiz mumkin.

Yuqoridagi kabi bir vaqtning o'zida o'zini-o'zi ko'p chaqiradigan rekursiv funksiyalar multiple recursion ham deyiladi. Bu kabi rekursiyalarning ishlash vaqti eksponensial oshib ketishi mumkin. Shuning uchun odatda bu kabi algoritmlar Dynamic Programmingga asoslangan memoization usulidan foydalangan holda optimallashtirib ishlatiladi.

Divide & Conquer

Rekursiyadan ajoyib tarzda foydalanadigan usullardan biri Divide & Conquer(D&C)dir.

Divide & Conquerda masala rekursiv tarzda kichikroq qism masalalarga bo'linadi (Divide), qism masalalar alohida ishlanganidan so'ng, javoblar birlashtiriladi (Conquer).

Merge Sort

D&Cga eng yaxshi misollardan biri bu Merge Sort saralash algoritmi hisoblanadi.

Merge Sortni qisqacha qilib quyidagi kod orqali tasvirlash mumkin:

func merge_sort(list a) -> list 
    if(len(a) == 1) // base case
        return a

    list left = a[0..len(a)/2]  // a ning chap yarmi
    list right = a[len(a)/2..len(a)] // a ning o`ng yarmi

    left = merge_sort(left) // chap qismni saralaymiz
    right = merge_sort(right) // o`ng qismni saralaymiz 

    return merge(left, right) // javoblarni birlashtiramiz

Xullas, algoritm \(a\) massivni saralash uchun quyidagilarni bajaradi:

a ni uzunligi \(1\) bo'lsa, uni saralashni hojati yo'q, shuning uchun a ni o'zini javob sifatida qaytaradi
aks holda, a ni teng hajmli left va right qism massivlarga bo'ladi
left va right qism massivlarni alohida rekursiv tarzda saralaydi
Saralangan left va right qism massivlarni merge(left, right) funksiyasi orqali birlashtiradi. merge(left, right)ni \(O(n)\) vaqtda implementatsiya qilish mumkin.

Base case rekursiyaning asosiy qismi bo'lib, u odatda rekursiya qachon to'xtashini ifodalaydi. Base case yetarlicha oson bo'ladi va unga javobni hisoblash uchun rekursiv chaqiruvlar kerak bo'lmaydi. Masalan, yuqoridagi kabi, massiv uzunligi \(1\) bo'lganda, rekursiv chaqiruvlar orqali saralashni hojati yo'q.

Yuqoridagi algoritmni Time Complexitysi(TC)ni quyidagi rekursiv ko'rinishda ham tasvirlash mumkin:

\[ T(n) = 2 * T(n / 2) + n \]

Ya'ni, uzunligi \(n\) bo'lgan massivni saralash TCsi uzunligi \(n/2\) bo'lgan 2 ta qism massivlarni(left va right) saralash TCsi hamda merge() funksiyasi ishlatadigan \(O(n)\) vaqtlar yig'indisidan iborat.

TCni bu kabi rekursiv ko'rinishda ishlatish anchagina noqulay. Shuning uchun uni rekursiv bo'lmagan Katta O notatsiyasi orqali ifodalaganimiz ma'qul. Buning uchun, avvalgidek funksiyaga chaqiruvlar soni \(k\) va funksiyadagi amallar soni \(m\) ni topamiz.

Uzunligi \(n\) bo'lgan a massiv uchun, merge_sort() bir funksiya chaqiruvida ko'pi bilan \(n\) ta amal bajaradi, aniqrog'i \(O(n)\) vaqt sarflaydi. Sababi ani left va right qism massivlarga bo'lish ham, merge() funksiyasi ham \(O(n)\) vaqtda ishlaydi.

\(k\) ni qiymatini hisoblash uchun quyidagi chaqiruv daraxtidan foydalanamiz:

merge_sort

Bu yerda funksiyaga chaqiruvlar qavatlar yordamida ifodalangan, ya'ni 0-qavatda uzunligi \(n\) bo'lgan qism massivlar, 1-qavatda uzungligi \(n/2\) bo'lgan, 2-qavatda uzunligi \(n/4\) bo'lgan va hokazo qism massivlar uchun funksiya chaqiruvlari keltirilgan. Ko'rinib turibdiki, \(i\)-qavatdagi chaqiruvlar soni \(2^i\) ga teng, qavatlar soni bo'lsa \(log_2(n)\) ga teng. Ya'ni, massiv uzunligi \(1\) bo'lguncha uni ikkiga bo'lyapmiz, necha marta bo'lishimiz mumkunligi esa \(log_2(n)\) ga teng bo'ladi.

Demak, umumiy chaqiruvlar sonini quyidagicha hisoblasak bo'ladi:

\[ k = \sum_{i=1}^{log_2(n)}2^i=2^{log_2(n)+1}=2 \times n \]

\(k=2n\) va \(m=n\) ekanini bilib ham oldik, endi xulosa qilib Time Complexityni \(O(n^2)\) deyishimiz mumkin. Bu Time Complexity to'g'ri, lekin yetarlicha aniq emas.

\(m=n\) bo'lishi, ya'ni merge_sort() ni har bir chaqiruvida ko'pi bilan \(n\) ta amal bajaralishi to'g'ri, lekin aniq amallar soni \(n\) dan ancha kichik bo'lishi mumkin. Masalan, oxirgi qavatda faqatgina \(1\) ta amal bajariladi.

Time Complexityni aniqroq hisoblash uchun, yana qavatlardan foydalanamiz. \(i\)-qavatda funksiya chaqiruvlari soni \(2^i\) ekanini bilamiz. Ana endi shu \(2^i\) chaqiruvning har birida, saralashimiz kerak bo'lgan qism massiv uzunligi \(n/2^i\) ga teng. Demak bu qavatdagi har bir chaqiruv uchun amallar soni ham \(n/2^i\) ga teng. Umumiy qilib aytganda, \(i\)-qavatdagi barcha amallar soni \(2^i \times n/2^i\) ga teng:

\[ T(n) = \sum_{i=1}^{log_2(n)}2^i \times n / 2^i=\sum_{i=1}^{log_2(n)} n=n \times log_2(n) \]

Shunday qilib, umumiy amallar soni \(nlog(n)\) ga teng, shu o'rinda Time Complexity ham \(O(n log n)\).

Amallar soni \(n logn\) bo'lishini har bir qavatdagi amallar soni \(n\) ekanidan ham ko'rish mumkin:

merge_sort2

Amalda, hamma D&C algoritmlarini ham bu kabi qavatlar orqali ifodalab analiz qilish oson emas. Masalan, quyidagi kabi TCni soddalashtirish qiyin bo'lib ketishi mumkin:

\[ T(n) = 3T(n/4) + \sqrt{n} \]

O'zi umuman ishlash vaqtini qavatlar orqali analiz qilish ko'p noqulayliklar olib keladi. Shuning uchun, quyida bu kabi D&C algoritmlarni osonroq analiz qilish yo'lini ko'rib chiqamiz.

Master Teoremasi

D&C algoritmlarini ishlash vaqtini umumiy qilib quyidagicha ifodalash mumkin:

\[ T(n) = a T(n/b) + f(n) \]

Bu yerda:

\(n\) kiruvchi ma'lumotlar hajmi
\(a\) qism masalalar soni (konstanta bo'lishi lozim)
har bir qism masala hajmi \(n/b\) (\(b > 1\))
\(f(n)\) shu funksiya chaqiruvi ichida bajariladigan amallar soni

Darhaqiqat, Merge Sort uchun, \(a=2\), \(b=2\) va \(f(n) = n\) bo'lgani uchun:

\[ T(n) = 2T(n/2)+n \]

Bu kabi rekursiv Time Complexitylarni osonroq hisoblash uchun Master Teoramasidan foydalanishimiz mumkin. Teoremaga ko'ra 3 xil holatda TCni aniqlash mumkin.

1-holat

Agar, qandaydir \(\epsilon > 0\) uchun, \(f(n) = O(n^{log_b{a}-\epsilon})\) shart bajarilsa:

\[ T(n) = \Theta(n^{log_b{a}}) \]

Masalan, quyidagi formula berilgan bo'lsin:

\[ T(n) = 3T(n/4)+\sqrt{n} \]

Bunda, \(a=3\), \(b=4\), \(f(n)=n^{1/2}\). Endi, \(log_{4}3\)ning qiymati \(1/2\) dan katta bo'lgani uchun, \(n^{1/2} < n^{log_{4}3}\) bo'ladi, bundan kelib chiqadiki:

\[ f(n) = O(n^{log_{4}3}) \]

1-holat sharti bajarildi, demak Time Complexity quyidagicha bo'ladi:

\[ T(n) = \Theta(n^{log_b{a}}) = \Theta(n^{log_{4}3}) \]

2-holat

Agar, \(f(n) = \Theta(n^{log_{b}a})\) shart bajarilsa:

\[ T(n) = \Theta(n^{log_{b}a}log_{b}n) \]

Masalan, quyidagi formula berilgan bo'lsin:

\[ T(n)=4T(n/2)+n^2 \]

Bunda \(a=4\), \(b=2\), \(f(n) = n^2\). Endi, \(log_{2}4\)ning qiymati \(2\) ga teng bo'lgani uchun, \(n^{log_{2}4}=n^2\), demak:

\[ f(n) = \Theta(n^{log_{2}4}) \]

2-holat sharti bajarildi, demak Time Complexity quyidagicha bo'ladi:

\[ T(n) = \Theta(n^{log_{b}a}log_{b}n)=\Theta(n^2log_{2}n) \]

3-holat

Agar, qandaydir \(\epsilon > 0\) uchun, \(f(n) = \Omega(n^{log_b{a}+\epsilon})\) shart bajarilsa:

\[ T(n) = \Theta(f(n)) \]

Shuningdek, bu holat uchun "regularity condition"ni tekshirish lozim:

\[ af(n/b) \leq kf(n) \]

Bu yerda \(k < 1\).

Masalan, quyidagi formula berilgan bo'lsin:

\[ T(n)=7T(n/3)+n^2logn \]

Bunda, \(a=7\), \(b=3\) va \(f(n) = n^2logn\). So'ng, \(n^{log_{3}7} < n^2\) bo'lgani uchun:

\[ f(n) = \Theta(n^{log_{3}7}) \]

3-holat sharti bajarildi, regularity condition ham bajarilishini ko'rsatish mumkin, demak Time Complexity quyidagicha bo'ladi:

\[ T(n) = \Theta(f(n)) = \Theta(n^2logn) \]

Boshqa holatlar

Master Teoremasini har doim ham ishlatib bo'lmaydi. Masalan \(a\) va \(b\) konstantalar uchun qo'yilgan shartlar bajarilmasa yoki yuqoridagi \(3\) ta holatdan birortasi ham bajarilmasa Master Teoremasi ishlamaydi.

Masalan:

\[ T(n) = 2T(n/2) + nlogn \]

hech bir holatga mos kelmaydi. Sababi \(f(n) = nlogn\) ni \(n^{log_{2}2}\) bilan farqi polinomial emas.

Shunday bo'lsada, Master Teoremasini ko'p hollarda qo'llasa bo'ladi va analizni ancha osonlashtiradi.

Amalda Master Teoremasini turli variantlari va ko'rinishlari mavjud. Masalan, shu keltirilgan misolni ham aslida Master Teoremasining ma'lum ko'rinishlarida ishlasa bo'ladi. Soddalik uchun, eng umumiy holatlarni ko'rib chiqdik. Agar Teoremaning isbotlariga qiziqsangiz, "Introduction to Algorithms"ni o'qishni tavsiya qilaman.

Space Complexity

Keyingi qismda Space Complexity haqida gaplashamiz.