Mavzu: Murakkablikning Theta Ө notation bo’yicha bahosini aniqlash. Mummolar & yechimlar

Mavzu: Murakkablikning Theta – Ө notation bo’yicha
bahosini aniqlash. Mummolar & yechimlar

Algoritmlar tahlili | 3-to‘plam (Asimptotik belgilar)

Biz asemptotik tahlil, eng yomoni, o'rtacha va eng yaxshi algoritmlarning eng yaxshi holatlarini muhokama qildik. Asimptotik tahlilning asosiy g'oyasi - mashinaga xos konstantalarga bog'liq bo'lmagan va algoritmlarni amalga oshirishni va taqqoslash uchun dasturlar tomonidan vaqtni talab qilmaydigan algoritmlarning samaradorligi o'lchoviga ega bo'lishdir. Asimptotik belgilar asimptotik tahlil uchun algoritmlarning vaqt murakkabligini ifodalovchi matematik vositalardir. Quyidagi 3 ta asimptotik belgilar asosan algoritmlarning vaqt murakkabligini ifodalash uchun ishlatiladi.



1) Θ Belgisi: Teta belgisi funksiyani yuqoridan va pastdan chegaralaydi, shuning uchun u aniq asimptotik harakatni belgilaydi.

Ifodaning Teta belgisini olishning oddiy usuli - past tartibli atamalarni tashlab, yetakchi konstantalarni e'tiborsiz qoldirishdir. Misol uchun, quyidagi ifodani ko'rib chiqing.
3n3 + 6n2 + 6000 = D(n3)
Pastki tartibli shartlarni tashlab qo'yish har doim yaxshi, chunki har doim bir raqam (n) bo'ladi, undan so'ng Θ(n3) ishtirok etgan konstantalardan qat'i nazar, D(n2) dan yuqori qiymatlarga ega bo'ladi.
Berilgan g(n) funksiya uchun biz D(g(n)) funksiyalar to‘plamini belgilaymiz.

D(g(n)) = {f(n): c1, c2 va n0 musbat konstantalar mavjud, shundayki 0 <= c1*g(n) <= f(n) <= c2*g(n) hamma uchun n >= n0}

Yuqoridagi ta'rif shuni anglatadiki, agar f(n) g(n) ning tetasi bo'lsa, f(n) qiymati har doim n ning katta qiymatlari uchun c1*g(n) va c2*g(n) oralig'ida bo'ladi (n >=). n0). Teta ta'rifi, shuningdek, f(n) n0 dan katta n qiymatlari uchun manfiy bo'lmasligini talab qiladi.
Misollar:

{ 100 , log (2000) , 10^4 } D(1) ga tegishli

{ (n/4) , (2n+3) , (n/100 + log(n)) } D(n) ga tegishli

{ (n^2+n) , (2n^2) , (n^2+log(n))} D( n^2) ga tegishli

D aniq chegaralarni beradi.

2) Big O belgisi: Katta O belgisi algoritmning yuqori chegarasini belgilaydi, u funksiyani faqat yuqoridan chegaralaydi. Misol uchun, Insertion Sort holatini ko'rib chiqing. Bu eng yaxshi holatda chiziqli vaqtni, eng yomon holatda esa kvadratik vaqtni oladi. Ishonch bilan aytishimiz mumkinki, Insertion sortning vaqt murakkabligi O(n^2). E'tibor bering, O(n^2) chiziqli vaqtni ham qamrab oladi.

Agar biz Insertion turining vaqt murakkabligini ifodalash uchun t belgisidan foydalansak, eng yaxshi va eng yomon holatlar uchun ikkita bayonotdan foydalanishimiz kerak:
1. Insertion Sortning eng yomon vaqt murakkabligi t(n^2).
2. Insertion Sortning eng yaxshi vaqt murakkabligi t(n).

Big O belgisi faqat algoritmning vaqt murakkabligining yuqori chegarasiga ega bo'lsa foydali bo'ladi. Ko'pincha biz algoritmga qarab yuqori chegarani osongina topamiz.

O(g(n)) = { f(n): c va n0 musbat konstantalar mavjud, shundayki 0 <= f(n) <= c*g(n) barcha n >= n0}



Misollar:

{ 100 , log (2000) , 10^4 } O(1) ga tegishli

U { (n/4) , (2n+3) , (n/100 + log(n)) } O (n) ga tegishli

U { (n^2+n) , (2n^2) , (n^2+log(n))} O(n^2) ga tegishli

Bu yerda U birlashishni bildiradi , biz buni shunday yozishimiz mumkin, chunki O aniq yoki yuqori chegaralarni beradi.

3) Ō belgisi: Big O belgisi funksiyaning asimptotik yuqori chegarasini ta'minlaganidek, Ō belgisi ham asimptotik pastki chegarani beradi.
Algoritmning vaqt murakkabligi bo'yicha pastki chegaraga ega bo'lsak, Ō belgisi foydali bo'lishi mumkin. Oldingi postda muhokama qilinganidek, algoritmning eng yaxshi ishlashi odatda foydali emas, Omega yozuvi uchtasi orasida eng kam qo'llaniladigan belgidir.

Berilgan g(n) funksiya uchun funksiyalar to‘plamini Ō(g(n)) bilan belgilaymiz.

GEEKSFORGEEKS

Algoritmlar tahlili | 3-to‘plam (Asimptotik belgilar)

Biz asemptotik tahlil, eng yomoni, o'rtacha va eng yaxshi algoritmlarning eng yaxshi holatlarini muhokama qildik. Asimptotik tahlilning asosiy g'oyasi - mashinaga xos konstantalarga bog'liq bo'lmagan va algoritmlarni amalga oshirishni va taqqoslash uchun dasturlar tomonidan vaqtni talab qilmaydigan algoritmlarning samaradorligi o'lchoviga ega bo'lishdir. Asimptotik belgilar asimptotik tahlil uchun algoritmlarning vaqt murakkabligini ifodalovchi matematik vositalardir. Quyidagi 3 ta asimptotik belgilar asosan algoritmlarning vaqt murakkabligini ifodalash uchun ishlatiladi.



1) Θ Belgisi: Teta belgisi funksiyani yuqoridan va pastdan chegaralaydi, shuning uchun u aniq asimptotik harakatni belgilaydi.

Ifodaning Teta belgisini olishning oddiy usuli - past tartibli atamalarni tashlab, yetakchi konstantalarni e'tiborsiz qoldirishdir. Misol uchun, quyidagi ifodani ko'rib chiqing.
3n3 + 6n2 + 6000 = D(n3)
Pastki tartibli shartlarni tashlab qo'yish har doim yaxshi, chunki har doim bir raqam (n) bo'ladi, undan so'ng Θ(n3) ishtirok etgan konstantalardan qat'i nazar, D(n2) dan yuqori qiymatlarga ega bo'ladi.
Berilgan g(n) funksiya uchun biz D(g(n)) funksiyalar to‘plamini belgilaymiz.

D(g(n)) = {f(n): c1, c2 va n0 musbat konstantalar mavjud, shundayki 0 <= c1*g(n) <= f(n) <= c2*g(n) hamma uchun n >= n0}

Yuqoridagi ta'rif shuni anglatadiki, agar f(n) g(n) ning tetasi bo'lsa, f(n) qiymati har doim n ning katta qiymatlari uchun c1*g(n) va c2*g(n) oralig'ida bo'ladi (n >=). n0). Teta ta'rifi, shuningdek, f(n) n0 dan katta n qiymatlari uchun manfiy bo'lmasligini talab qiladi.



Misollar:

{ 100 , log (2000) , 10^4 } D(1) ga tegishli

{ (n/4) , (2n+3) , (n/100 + log(n)) } D(n) ga tegishli

{ (n^2+n) , (2n^2) , (n^2+log(n))} D( n^2) ga tegishli

D aniq chegaralarni beradi.

2) Big O belgisi: Katta O belgisi algoritmning yuqori chegarasini belgilaydi, u funksiyani faqat yuqoridan chegaralaydi. Misol uchun, Insertion Sort holatini ko'rib chiqing. Bu eng yaxshi holatda chiziqli vaqtni, eng yomon holatda esa kvadratik vaqtni oladi. Ishonch bilan aytishimiz mumkinki, Insertion sortning vaqt murakkabligi O(n^2). E'tibor bering, O(n^2) chiziqli vaqtni ham qamrab oladi.
Agar biz Insertion turining vaqt murakkabligini ifodalash uchun t belgisidan foydalansak, eng yaxshi va eng yomon holatlar uchun ikkita bayonotdan foydalanishimiz kerak:
1. Insertion Sortning eng yomon vaqt murakkabligi t(n^2).
2. Insertion Sortning eng yaxshi vaqt murakkabligi t(n).

Big O belgisi faqat algoritmning vaqt murakkabligining yuqori chegarasiga ega bo'lsa foydali bo'ladi. Ko'pincha biz algoritmga qarab yuqori chegarani osongina topamiz.

O(g(n)) = { f(n): c va n0 musbat konstantalar mavjud, shundayki 0 <= f(n) <= c*g(n) barcha n >= n0}



Misollar:

{ 100 , log (2000) , 10^4 } O(1) ga tegishli

U { (n/4) , (2n+3) , (n/100 + log(n)) } O (n) ga tegishli

U { (n^2+n) , (2n^2) , (n^2+log(n))} O(n^2) ga tegishli

Bu yerda U birlashishni bildiradi , biz buni shunday yozishimiz mumkin, chunki O aniq yoki yuqori chegaralarni beradi.

3) Ō belgisi: Big O belgisi funksiyaning asimptotik yuqori chegarasini ta'minlaganidek, Ō belgisi ham asimptotik pastki chegarani beradi.
Algoritmning vaqt murakkabligi bo'yicha pastki chegaraga ega bo'lsak, Ō belgisi foydali bo'lishi mumkin. Oldingi postda muhokama qilinganidek, algoritmning eng yaxshi ishlashi odatda foydali emas, Omega yozuvi uchtasi orasida eng kam qo'llaniladigan belgidir.

Berilgan g(n) funksiya uchun funksiyalar to‘plamini Ō(g(n)) bilan belgilaymiz.

ũ (g(n)) = {f(n): c va n0 musbat konstantalar mavjud, shundayki 0 <= c*g(n) <= f(n) barcha n >= n0} bo'ladi.

Keling, bu erda bir xil Insertion tartiblash misolini ko'rib chiqaylik. Insertion Sort ning vaqt murakkabligi Ō(n) sifatida yozilishi mumkin, lekin qo'shish tartibi haqida unchalik foydali ma'lumot emas, chunki bizni odatda eng yomon va ba'zan o'rtacha holatda qiziqtiramiz.

Misollar:

{ (n^2+n) , (2n^2) , (n^2+log(n))} Ō(n^2) ga tegishli

U { (n/4) , (2n+3) , (n/100 + log(n)) } O (n) ga tegishli

U { 100 , log (2000) , 10^4 } Ō(1) ga tegishli

Bu yerda U birlashmani bildiradi, buni shunday yozishimiz mumkin, chunki Oh aniq yoki pastki chegaralarni beradi
Asimptotik belgilarning xususiyatlari:
Ushbu uchta belgining ta'rifini ko'rib chiqqanimizdan so'ng, keling, ushbu belgilarning ba'zi muhim xususiyatlarini muhokama qilaylik.

1. Umumiy xususiyatlar:

Agar f(n) O(g(n)) bo'lsa, a*f(n) ham O(g(n)) bo'ladi; bu yerda a doimiy.

Misol: f(n) = 2n²+5 O(n²)

u holda 7*f(n) = 7(2n²+5) = 14n²+35 ham O(n²) boʻladi.

Xuddi shunday, bu xususiyat ham T, ham Ō belgilarini qondiradi.

Aytishimiz mumkin

Agar f(n) t(g(n)) bo'lsa, a*f(n) ham D(g(n)) bo'ladi; bu yerda a doimiy.
Agar f(n) Ō (g(n)) bo'lsa, a*f(n) ham Ō (g(n)) bo'ladi; bu yerda a doimiy.

2. Transitiv xususiyatlar:

Agar f(n) O(g(n)) va g(n) O(h(n)) bolsa f(n) = O(h(n)) .

Misol: agar f(n) = n, g(n) = n² va h(n)=n³

n O(n²) va n² O(n³)
u holda n - O(n³)

Xuddi shunday, bu xususiyat ham T, ham Ō belgilarini qondiradi.

Aytishimiz mumkin
Agar f(n) t(g(n)) va g(n) t(h(n)) bo‘lsa, f(n) = D(h(n)) .
Agar f(n) Ō (g(n)) va g(n) Ō (h(n)) bo'lsa, f(n) = Ō (h(n)) bo'ladi.
3. Refleksiv xususiyatlar:

Refleksiv xususiyatlar tranzitivdan keyin tushunish har doim oson.

Agar f(n) berilgan boʻlsa, f(n) O(f(n)) boʻladi. Chunki f(n) ning MAKSIMAL QIYMATI f(n) O'ZI bo'ladi!

Demak, x = f(n) va y = O(f(n) har doim refleksiv munosabatda bo'ladi.

Misol: f(n) = n² ; O(n²) yaʼni O(f(n))

Xuddi shunday, bu xususiyat ham T, ham Ō belgilarini qondiradi.

Buni aytishimiz mumkin:

Agar f(n) berilgan bo‘lsa, f(n) t(f(n)) bo‘ladi.

Agar f(n) berilgan bo'lsa, f(n) Ō (f(n)) bo'ladi.

4. Simmetrik xossalar:

Agar f(n) t(g(n)) bo'lsa, g(n) t(f(n)) bo'ladi.

Misol: f(n) = n² va g(n) = n²

u holda f(n) = D(n²) va g(n) = D(n²)

Bu xususiyat faqat t belgisi uchun javob beradi.

5. Simmetrik xossalarni ko‘chirish:

Agar f(n) O(g(n)) bo'lsa, g(n) Ō (f(n)) bo'ladi.

Misol: f(n) = n , g(n) = n²

u holda n O(n²) va n² Ō (n) ga teng.

Bu xususiyat faqat O va Ō belgilarini qanoatlantiradi.

6. Yana bir qancha xususiyatlar:

1.) Agar f(n) = O(g(n)) va f(n) = ũ(g(n)) bo'lsa, f(n) = D(g(n))

2.) Agar f(n) = O(g(n)) va d(n)=O(e(n)) boʻlsa.
u holda f(n) + d(n) = O( max( g(n), e(n) ))
Misol: f(n) = n ya'ni O(n)
d(n) = n², ya'ni O(n²)
u holda f(n) + d(n) = n + n², ya'ni O(n²)

3.) Agar f(n)=O(g(n)) va d(n)=O(e(n)) boʻlsa.

keyin f(n) * d(n) = O( g(n) * e(n) )
Misol: f(n) = n ya'ni O(n)
d(n) = n², ya'ni O(n²)
u holda f(n) * d(n) = n * n² = n³ ya'ni O(n³)

___________________

Eslatma: Agar f(n) = O(g(n)) bo'lsa, g(n) = Ō(f(n))

Mashq:

Quyidagi bayonotlardan qaysi biri to'g'ri/to'g'ri?

1. Tezkor saralashning vaqt murakkabligi t(n^2)

2. Tezkor saralashning vaqt murakkabligi O(n^2)

3. Istalgan ikkita f(n) va g(n) funksiyalar uchun f(n) = D(g(n)) bo‘ladi, agar f(n) = O(g(n)) va f(n) bo‘lsa. ) = Ō(g(n)).

4. Barcha kompyuter algoritmlarining vaqt murakkabligi Ō(1) shaklida yozilishi mumkin.

Muhim havolalar:

Kichik o va kichik omega deb nomlangan yana ikkita belgi mavjud. Kichik o qat'iy yuqori chegarani ta'minlaydi (tenglik sharti Katta O'dan olib tashlanadi) va kichik omega qat'iy pastki chegarani ta'minlaydi (katta omegadan tenglik sharti olib tashlanadi)

Algoritmlar tahlili | 4-to'plam (Looplar tahlili)

Algoritm tahlili bo'yicha so'nggi maqolalar.

Adabiyotlar:

Lec 1 | MIT (Algoritmlarga kirish)

Ushbu maqola Abhay Rathi tomonidan taqdim etilgan. Agar biror narsa noto'g'ri bo'lsa yoki yuqorida muhokama qilingan mavzu haqida ko'proq ma'lumot almashishni istasangiz, sharhlaringizni yozing.