Katta O. Algoritmlar va Murakkablik. 1-Qism

Algoritmlar samaradorligini o'lchash fundamental muammolardan biri hisoblanadi. Uni o'rganmay turib algoritmlarni o'rganib bo'lmaydi.

Ushbu maqolada algoritm murakkabligi va "Big O notation" haqida gaplashamiz.

Muammo

Keling quyidagi leetcode masalasini ishlaymiz:
drawing
Masalada aytilishicha, turli qiymatdagi butun sonlardan iborat, o'sish tartibida saralangan massiv berilgan. Berilgan qandaydir target soni uchun, agar u massivda bo'lsa, u turgan indeksini, aks holda, massivga qo'shganimizda qaysi o'rinda bo'lishini topishimiz kerak.

Masalaning yechimi ham qiyin emas. Aytaylik, oddiygina massiv elementlarini birma-bir ko'rib chiqib berilgan sonning indeksini topsak bo'ladi.

Ana endi muammo: bizda masalaga yechim bor va u to'g'ri ishlaydi, lekin bu yechim yetarlicha tezmi? Balkim bundan ko'ra tezroq algoritm topish mumkindir? Bu kabi savollarga javob topish uchun algoritmlarning tezligini "o'lchashimiz" lozim!

Algoritm tezligi

Agar har bir algoritmning tezligini izchillik bilan "o'lchash"ni imkonini topsak, u holda bir nechta algoritmlarni bir biri bilan solishtirib, eng tez va yaxshisini saralab olishimiz mumkin bo'ladi. Ammo ularni qanday o'lchaymiz?

Ishlash vaqti bilan o'lchash

Eng intuitiv yechim, albatta, algoritmni dasturini tuzib, uni ishlatib ko'rish va ishlashi uchun qancha vaqt ketqizganini o'lchash. Ya'ni, dasturning "running time" yoki "execution time"i.

Kutilmagan bo'lsada, bu usul eng yomon va izchil bo'lmagan usullardan hisoblanadi. Sabablari quyidagicha:

Dasturlash tillari farqi. Bu yechimda, algoritmni ishlatib ko'rish uchun avval uni dasturini tuzishga to'g'ri keladi. Dasturlash tillari esa har xil tezlikda ishlaydi. Masalan bir xil algoritmni C++ dagi ko'rinishi Pythondagi ko'rinishdan tez ishlashi mumkin.
Muhitning farqi. Tuzgan dasturimizni qandaydir muhit yoki kompyuterda ishga tushiramiz. Kompyuterlarni kuchi turli xil bo'lgani tufayli, dastur kuchliroq kompyuterda tezroq, kuchsizrog'ida sekinroq ishlashi mumkin.
Kiruvchi ma'lumotlar farqi. Har bir algoritm ma'lum bir (kiruvchi) ma'lumot bilan ishlaydi. Algoritmni ishlash tezligi ham shu kiruvchi ma'lumotga qarab har xil bo'ladi. Tezlikni ishlash vaqti orqali solishtirish jarayonida, berilgan ma'lumotlar haqqoniy ekanini ta'minlashimiz shart. Tasavvur qiling, ikki xil algoritm bor: birinchi algoritm \(n <= 5\) bo'lganda, ikkinchisi esa \(5 < n <= 10^6\) bo'lganda tez ishlaydi. Ana endi, bu ikki algoritmni faqat \(n <= 5\) bo'lgan holatda tezligini o'lchasak, birinchi algoritm tezroq bo'lib chiqadi. Aslida esa, ancha ko'proq hollarda ikkinchi algoritm tezroq.
Deterministik emasligi. Mayli endi, dasturni ma'lum dasturlash tilida yozib, ma'lum kompyuterda ishlatib ko'rdik. Hatto bu holda ham, ishlash vaqti doim bir xil chiqmaydi. Bunga sabab, dastur ishlash vaqti juda ham ko'p faktorlarga, xususan operatsion tizim, undagi "scheduler", protsessor bandligi va h.z.larga bog'liq.

Bu muammolarning hammasi yuqoridagi oltin qoidani buzadi: izchillik yo'qligi.

Yolg'onchi Leetcode

Leetcodeni quyidagi xususiyatini ko'rgandirsiz:

big_o

Suratda dastlab berilgan masala uchun C++da yozilgan sodda yechim keltirilgan. Qiziq joyi esa, bu yechim 0 ms vaqtda ishlab, boshqa yechimlarning 100%idan ko'ra tezroq ishlagan.

To'g'ri, bu C++da yozilgan yechim, leetcode serverlarida 0 ms(yaxlitlaganda)da ishlagan va haqiqatdan ham bu masala uchun 0 ms dan ko'ra tezroq ishlaydigan yechim yo'q.

Ammo, bu ma'lumot umuman keraksiz. 100% tez ishladi degani, yechim eng tez yoki eng yaxshi yechim ekanini bildirmaydi. Sababini esa yuqorida keltirib o'tilgan 4 ta muammodan ko'rishingiz mumkin. Ya'ni bu dastur, ma'lum dasturlash tilida yozilib, ma'lum serverda, ma'lum vaqtda ishga tushirilgan va tez ishlagan.

Yanada qiziq tomoni, bu dasturda keltirilgan algoritm aslida tez emas, dasturda ko'rib turganingizdek, for orqali massiv uzunligigacha iteratsiya qilyapmiz. Ya'ni uzunligi \(n\) bo'lgan massiv uchun bu dastur ko'pi bilan \(n\) ta amal bajaradi.

Quyidagi dasturda esa, for doim \(14\) marta iteratsiya qiladi va javobni topadi:

big_o

\(7\) ms va \(22.56 \%\) ?? Vaholanki, bu yechim avvalgisidan ko'ra ancha tezroq ishlashi lozim. Masalan, \(n=1000\) bo'lganda, eng yomon holatda birinchi yechim \(1000\) marta iteratsiya qiladi. Ikkinchi yechim bo'lsa bor yo'g'i \(14\) ta.

Bunaqa bo'lishini sababi, bu dasturlarni tekshiradigan testlar yetarlicha katta emasligi, eng yomon holatlarni hisobga olinmaganligi, yoki oddiygina leetcode serverlarining band bo'lganligi bo'lishi mumkin.

Bir so'z bilan aytganda, dasturni ishlashiga ketadigan vaqt algoritm haqida deyarli hech nima aytmaydi!

P.S. Ikkinchi yechimni aynan o'zini bir necha marta qayta yuborishlardan so'ng, unda ham \(0\) ms \(100 \%\) natijaga erishdim :).

Time Complexity

Yuqoridagi muammolardan kelib chiqqan holda, algoritmni dasturini tuzib ishlatib ko'rish yaxshi fikr emas ekan. Buning o'rniga algoritmni o'zini o'rganib, undagi amallar soniga e'tibor qilsakchi?

Bundan buyog'iga algoritmni "tezligi"ni emas, uning murakkabligini, boshqacharoq aytganda Time Complexitysini o'rganamiz. Nega aynan "murakkablik"? Tez orada bilib olamiz. Hozir esa bizga kerakli tushunchalarni kelishib olaylik.

Pseudocode

Pseudocode algoritmni ifodalashning bir usuli bo'lib, u algoritm uchun tuzilgan dasturga juda ham o'xshab ketadi.

Pseudocode bu dasturlash tili emas, ammo unda boshqa eng ko'p ishlatiladigan dasturlash tillaridagi sintaksis ishlatiladi. Quyida "Insertion Sort" algoritmi uchun pseudocodeni ko'rishingiz mumkin¹:

INSERTION-SORT(A, n)
for i = 2 to n
    key = A[i]
    // Insert A[i] into the sorted subarray A[1 : i – 1].
    j = i – 1
    while j > 0 and A[j] > key
        A[j + 1] = A[j]
        j = j – 1
    A[j + 1] = key

Oddiy kod kompyuterda kompilyatsiya bo'lishi va ishlashi uchun yozilsa, pseudocode odamlar o'qib tushunishi uchun yoziladi. Shuning uchun, pseudocodeda yozishni qoidasi yo'q, muhimi tushunarli bo'lsa bo'ldi, qaysi turdagi sintaks ishlatish muhim emas.

Ana endi pseudocode orqali algoritmdagi operatsiyalar sonini sanashimiz osonroq bo'ladi.

RAM model

Time Complexityni o'lchashda bajarilgan operatsiyalar sonidan foydalanishga kelishdik. Ammo "operatsiya"ni qanday ta'riflaymiz? Turli mashinalarni xarakteristikalari turli bo'lgani uchun, operatsiyalarni qandaydir "jismoniy" qurilma operatsiyalarga moslab hisoblay olmaymiz.

Random Access Machine shunaqangi hisoblash modeliki, u zamonaviy kompyuterlardagi operatsiyalarga asoslangan abstrakt mashinadan tashkil topgan.

Abstract? Ha, RAM modeli deganda, yagona protsessorli, ammalar ketma-ket bajariladigan(parallelism yo'q) va har bir amal bir xil vaqtda ishlaydigan mashinani tasavvur qilish mumkun. Ya'ni, abstrakt mashina mavjud jismoniy qurilmalarni "soddalashtirilgan" ko'rinishi, amalda kompyuterlar bunday ishlamaydi.

Random Access? RAMda qandaydir "random" xotira qismiga "access"(murojaat) qilish konstant vaqt oladi. Umuman olganda, RAMda xotiradagi ma'lumotlarni ishlatish va saqlash boshqa barcha operatsiyalar kabi bir xil vaqt oladi.

RAMga bundan ancha yaxshi, formalroq ta'rif berish mumkin. Uning asosiy ma'nosi esa zamonaviy kompyuterlarni murakkab detallarini "yashirgan" holda, algoritmni osonroq analiz qilish imkonini beradi.

Xulosa qilib aytadigan bo'lsak, buyog'iga algoritmni analiz qilayotganimizda va operatsiyalar haqida so'z borganda, aynan shu abstrakt mashinada ishlaydigan operatsiyalarni nazarda tutamiz. Bu operatsiyalar esa zamonaviy kompyuterlar konstant vaqtda bajara oladigan darajada oddiy bo'lishi lozim. Masalan, RAMda massivni saralab beradigan operatsiya bo'lishi haqiqatdan yiroq.

Yanada soddalashtirish

RAM haqida o'rgandik, lekin baribir bitta operatsiya aynan qanday ko'rinishida bo'lishiga kelishmadik. Masalan quyidagi kodda nechta operatsiya bajariladi?

if(a > b)
    c = a * b + 3;
else
    c = a - b;

Bunda if ni ichidagi solishtirish bitta amalmi? a*b hamda a*b+3 alohida amalmi?

Bu kabi tushunmovchiliklarni oldini olish uchun, aynan shu maqola uchun: pseudocodedagi bitta qator bitta amal bo'lsin.

Masalan, yuqoridagi koddagi bajariladigan amallar soni 4 ga teng.

Input Size

Kiruvchi ma'lumotlar hajmi, ya'ni Input Size algoritm ishlatadigan ma'lumotlar hajmini bildiradi. Masalan, saralash algoritmi uchun, massiv uzunligi input size bo'lishi mumkin. O'zi umuman ko'plab kiruvchi ma'lumotlarni massiv ko'rinishida tasvirlab, uning uzunligini input size qilib olish mumkin.

Input size nimaga kerak? Algoritm bajaradigan operatsiyalar soni aynan shu input sizega bog'liq. Albatta 10 ta elementli massivni saralash, 1000 ta elementli massivni saralashdan ko'ra ancha kam operatsiyalar talab qiladi.

Shuning uchun ham algoritm time complexitysida input size, yoki umuman algoritm ishlashiga ta'sir o'tkazuvchi o'zgaruvchilar inobatga olinishi shart.

Masalan, quyidagi kodni ko'raylik:

for i = 1 to n
    swap(a[i], a[n - i + 1])
    count = count + 1

Birinchi sikl \(n\) marta takrorlangani uchun, koddagi 3 ta qator ham \(n\) martadan bajariladi. Shunday qilib, umumiy algoritm \(3*n\) ta amal bajaradi.

Insertion Sort analizi

Allaqachon operatsiyalar sonini qanday sanashimizni tushungandirsiz. Har bir qatorni nechi marta ishlashini sanaymiz va yig'indini formula ko'rinishida yozamiz.

Yaxshiroq tasavvurga ega bo'lish uchun avvalroq keltirilgan Insertion Sort algoritmini xuddi shu tarzda tahlil qilishga harakat qilib ko'ramiz:

INSERTION-SORT(A, n)
for i = 2 to n
    key = A[i]
    // Insert A[i] into the sorted subarray A[1 : i – 1].
    j = i – 1
    while j > 0 and A[j] > key
        A[j + 1] = A[j]
        j = j – 1
    A[j + 1] = key

Bu yerda endi har bir qator necha marta ishlashini topish biroz murakkabroq. Ayniqsa, while necha marta bajarilishi A[] massiv qiymatlariga bog'liq. Ya'ni, ma'lum bir "input size" uchun algoritm ishlash tezligi, odatda nafaqat input sizega, balki shu inputdagi qiymatlarga ham bog'liq.

Ushbu algoritm ishlash vaqti massiv elementlari qiymatiga bog'liq bo'lgani tufayli, keling algoritm ishlashini eng yaxshi(best case) va eng yomon (worst case) holatlarda ko'rib chiqaylik.

Best Case

Best Case deb algoritm uchun "eng yaxshi", ya'ni, algoritm eng tez ishlaydigan holat yoki kiruvchi ma'lumot tushuniladi.

Insertion Sort uchun eng yaxshi holat massiv elementlari allaqachon saralangan bo'lganida bo'ladi, bunda while sikli ichidagi kod hech qachon bajarilmaydi:

INSERTION-SORT(A, n)
for i = 2 to n                                              // n - 1 marta
    key = A[i]                                              // n - 1 marta 
    // Insert A[i] into the sorted subarray A[1 : i – 1].
    j = i – 1                                               // n - 1 marta
    while j > 0 and A[j] > key                              // n - 1 marta 
        A[j + 1] = A[j]                                     // 0 marta
        j = j – 1                                           // 0 marta
    A[j + 1] = key                                          // n - 1 marta

Agar ishlash vaqtini, \(T(n)\) funksiya orqali ifodalasak, bu holatda:

\[ T(n) = (n - 1) + (n - 1) + (n - 1) + (n - 1) + 0 + 0 + (n - 1) = 5n - 5 \]

bo'ladi. Buni esa umumiyroq qilib:

\[ T(n) = 5n - 5 = an + b \]

ko'rinishida yozish mumkin. Bu yerda \(a\) va \(b\) lar qandaydir konstantalar. Demak, bu yerda complexity \(n\) ga bog'liq chiziqli funksiyadan iborat bo'lmoqda.

Worst Case

Worst Case deb, algoritm uchun "eng yomon", algoritm eng ko'p vaqt sarflaydigan holat yoki inputga aytiladi.

Insertion Sort uchun eng yomon holat massiv elementlari teskari tartibda saralangan bo'lsa kuzatiladi. Bunda while sikli \(i\) - iteratsiyada aynan \(i\) marta ishlaydi. \(i = 2, 3, ..., n\) bo'lgani uchun while ichidagi kod \(n (n - 1) / 2\) marta ishlaydi. Aniqrog'i, har bir qator uchun qiymatlar quyidagicha bo'ladi:

INSERTION-SORT(A, n)
for i = 2 to n                                              // n - 1 marta
    key = A[i]                                              // n - 1 marta 
    // Insert A[i] into the sorted subarray A[1 : i – 1].
    j = i – 1                                               // n - 1 marta
    while j > 0 and A[j] > key                              // n*(n+1)/2-1 marta 
        A[j + 1] = A[j]                                     // n*(n-1)/2 marta
        j = j – 1                                           // n*(n-1)/2 marta
    A[j + 1] = key                                          // n - 1 marta

Umumiy operatsiyalar sonini \(T(n)\) funksiya orqali ifodalaymiz:

\[ T(n) = (n - 1) + (n - 1) + (n - 1) + \frac{n(n + 1)}{2} + \frac{n(n-1)}{2} +\frac{n(n-1)}{2}+(n - 1) \]

Buni soddalashtirsak:

\[ T(n) = 4(n-1) + \frac{n(n+1)}{2} + n(n-1) = \frac{3n^2-n}{2} + 4n - 4 \]

Bu esa kvadratik funksiya bo'lgani uchun, uni quyidagicha yozish mumkin:

\[ T(n) = \frac{3n^2-n}{2} + 4n - 4 = an^2 + bn + c \]

Bu yerda \(a\), \(b\) va \(c\) biror bir konstantalar.

Nega Worst Case?

Dasturlashda Best Casedan ko'ra Worst Case muhimorq.

Bir tomondan tuzgan dasturimiz barcha hollarda to'g'ri ishlashi va ishonchli bo'lishi lozim. Eng yomon holatni baribir ko'rishimiz kerak.

Shuning uchun ham, qolgan hollardan ko'ra eng yomon holatga diqqatimizni qaratsak bo'ladi. Agar algoritm eng yomon holat uchun yetarlicha tez ishlasa, qolgan holatlar uchun ham yetarlicha tez ishlaydi.

Shunday ekan, buyog'iga murakkablik haqida so'z borganda, eng yomon holat yoki input bilan ishlayapmiz deb tasavvur qilishingiz mumkin.

Order of growth

Hozirni o'zida Insertion Sortni best case time complexitysi \(T(n) = an + b\) va worst case complexitysi \(T(n) = an^2+bn+c\) deb xulosa qilishimiz mumkin edi. Ammo bu ham yetarli emas.

Ko'pchilik algoritmlarni bu ko'rinishda analiz qilish yetarlicha oson emas. Algoritm murakkabroq bo'lgani sari, funksiya hadlari soni oshib, murakkablashib boraveradi. Shuning uchun biz yana bir soddalashtirish kiritamiz.

Bizga aniq operatsiyalar soni kerak emas, aks holda ko'plab keraksiz detallar bilan ishlashimizga to'g'ri keladi. Biz qiziqadigan narsa esa "order of growth" ya'ni o'sish sur'atidir.

Masalan, Insertion sortning worst case time complexitysini \(T(n) = an^2+bn+c\)ni o'rniga, oddiygina \(n^2\) ko'rinishda ifodalashimiz yetarli. Bu funksiyada, biz nafaqat kichikroq darajali \(bn+c\) hadlarni balkim, ularni oldidagi \(a\), \(b\), \(c\) koeffitsientlarni ham inobatga olmayapmiz. Sababi, funksiyani o'sish surati aynan \(n^2\) hadga ko'proq bog'liq.

Tasavvur qiling, bizda \(n^2/100 + 100n + 17\) vaqtda ishlaydigan algoritm bor. Bunda \(100n\) hadi \(n^2/100\)dan ko'ra muhimroq ko'rinishi mumkin, lekin bu holda ham kattaroq darajali \(n^2\) hadi muhimroq rol o'ynaydi. \(n\) ni qiymati \(10000\) dan oshganda \(n^2/100\) hadi \(100n\) dan oshib ketgani sababli, \(100n\) va \(17\) hadlari funksiya o'sishiga ortiqcha ta'sir o'tkazmaydi.

Katta O

Demak, algoritmni ishlash vaqtini analiz qilish uchun, undagi operatsiyalar soni va input sizega bog'liq funksiya tuzib, uni o'sish suratini topishimiz mumkin ekan.

Buni endi formalroq ko'rinishda ifodalash uchun maxsus "notation" bilan tanishamiz.

O'sish suratini(ishlash vaqtini emas) ifodalash uchun quyidagi 3 ta notationdan foydalanamiz.

Big \(O\) Notation

Katta \(O\), funksiyaning o'sish surati uchun upper boundni, ya'ni yuqori chegarani ifodalaydi.

Masalan \(7n^3+100n^2-20n+6\) funksiyaning o'sish surati \(n^3\) bo'lishini oldinroq o'rgangan edik. Bu funksiya kamida \(n^3\) darajada o'sgani uchun, bu funksiyani \(O(n^3)\) ko'rinishida yozishimiz mumkin.

Eng qiziq joyi, bu funksiyani \(O(n^4)\) deb ham ifodalashimiz mumkin. Sababi, o'sish surati \(n^3\) va bu \(n^4\) dan kichik, shuning uchun \(O(n^4)\) ham \(7n^3+100n^2-20n+6\) uchun upper bound bo'lishi mumkin. O'zi umuman bu funksiyani \(O(n^5)\), \(O(n^6)\), ... deb ham yozishimiz mumkin.

Shu sababdan, \(O\) notation aniq o'sish suratini ifodalamaydi. Qandaydir algoritm \(O(n^3)\) bo'ladi deganimiz bilan, uning asl o'sish surati n^2 yoki n ham bo'lishi mumkin, lekin n^4 bo'lishi mumkin emas.

big_o

Formalroq ta'riflaydigan bo'lsak, Qandaydir \(f(n)\) funksiya uchun \(f(n)=O(g(n))\) bo'lishi uchun, shunaqangi musbat \(n_0\) va \(c\) o'zgarmaslar bo'lishi kerakki, \(n_0\)da va uning o'ng tarafida \(f(n)\) ning qiymati doim \(cg(n)\) da yoki undan pastda bo'lishi lozim.

Masalan, \(5n^2 + 100n + 17\) funksiya \(O(n^2)\) bo'la oladi, sababi masalan \(c=6\) bo'lganda, \(n_0 = 101\) dan boshlab \(5n^2 + 100n + 17\) funksiya \(6n^2\) dan pastda turadi.

Big \(\Omega\) Notation

\(\Omega\) notation funksiyaning o'sish surati uchun lower boundni, ya'ni quyi chegarani ifodalaydi. Masalan, \(7n^3+100n^2-20n+6\) funksiya ko'pi bilan \(n^3\) darajada o'sgani uchun, uni \(\Omega(n^3)\) ko'rinishida ifodalashimiz mumkin. Xuddi shu tarzda u \(\Omega(n^2)\) yoki \(\Omega(n)\) bo'lishi ham mumkin

\(\Omega\)(o'qilishi omega) ham xuddi \(O\) kabi aniq o'sish suratini ifodalamaydi. \(\Omega(n^2)\) bo'lgan funksiyaning o'sish surati \(n^3\) yoki \(n^4\) bo'lishi mumkin. Lekin \(n\) bo'la olmaydi.

big_o

\(\Omega\) notationni ham formal ta'riflasak bo'ladi. Qandaydir \(f(n)\) funksiya uchun \(f(n)=\Omega(g(n))\) bo'lishi uchun, shunaqangi musbat \(n_0\) va \(c\) o'zgarmaslar bo'lishi kerakki, \(n_0\) da va uning o'ng tarafida \(f(n)\)ning qiymati doim \(cg(n)\) da yoki undan yuqorida bo'lishi lozim.

Big \(\Theta\) Notation

\(O\) va \(\Omega\) notationlar yuqori va quyi chegarani ifodalagani uchun, ularni quyidagi tengsizlik orqali tasavvur qilish mumkin:

\[ \Omega() \leq T() \leq O() \]

Bu yerda \(T(n)\) o'sish suratini bildiruvchi funksiya.

\(\Theta\)(o'qilishi Tseta) notation funksiya uchun aniq o'sish suratini ifodalaydi. Agar qandaydir \(f(n)\) funksiya bir vaqtning o'zida ham \(O(f(n))\) va \(\Omega(f(n))\) bo'lsa, u holda u \(\Theta(f(n))\) ham bo'ladi.

Masalan, yuqoridagi misolda \(7n^3+100n^2-20n+6\) funksiya ham \(\Omega(n^3)\) va \(O(n^3)\) bo'lgani uchun, u \(\Theta(n^3)\) ham bo'ladi.

big_o

Qandaydir \(f(n)\) funksiya uchun \(f(n)=\Theta(g(n))\) bo'lishi uchun, shunaqangi musbat \(n0\), \(c_1\) va \(c_2\) o'zgarmaslik bo'lishi kerakki, \(n_0\)da va uning o'ng tarafida \(f(n)\)ning qiymati doim \(c_1g(n)\) va \(c_2g(n)\) o'rtasida bo'lsin.

Misollar

Amalda algoritmni murakkabligini hisoblashda bu kabi funksiyalar va formal matematik ta'riflar kerak emas. Bularning barchasi bu tushuncha ortidagi mohiyatni tushunishda yordam beradi(va yordam berdi deb umid qilaman :).

Keling endi, murakkablikni o'lchashga bir nechta misol ko'raylik:

for(i = 1; i <= 2 * n; i ++)
    sum += i

Bu oddiy misolda, forni o'zi ham, ichidagi kod ham \(2n\) marta ishlaydi. Jami amallar soni \(4n\) desa ham bo'ladi. Tabiiyki bu \(O(n)\), o'sish sur'atini \(4\) emas, \(n\) hal qilmoqda.

for(i = 1; i <= 100 * n; i ++)
    sum += i

Xuddi shu kod, ammo endi sikl \(100n\) marta bajarilmoqda. Qizig'i, bu ham \(O(n)\)! \(100\) katta son bo'lgani bilan, o'zgarmas bo'lgani uchun, \(n\) ni qiymati oshgani sari o'sish sur'atiga ta'siri ham o'zgarishsiz qoladi. Shuning uchun, murakkablik uchun \(100\)ni qoldirib ketsak bo'ladi.

big_o

Yuqoridagi grafik²da ayrim chiziqli va kvadratik funksiyalarni ko'rishingiz mumkin. Konstantalar funksiyani shaklini o'zgartirmaydi, faqat chiziqni keskinligini oshirishi mumkin.

Shuni e'tiborga olish kerakki, murakkablik \(O(n)\) degani, amalda kod \(n\) ta amal bajaradi degani emas. Amalda baribir kompyuter \(100n\) ta amal bajaradi. Shuning uchun, katta o'zgarmas mavjud payti maxsus hol sifatida ko'rilishi va e'tibordan chetda qoldirilmasligi lozim. Fanda, bunday holatni "katta konstant faktorli O(n)" deb ham aytishadi.

for(i = 1; i <= n; i ++)
for(j = i; j <= n; j ++)
    sum += a[i][j]

for(int i = 1; i <= 3*n; i ++)
    print(ans[i])

if(ans[0] == ans[3*n])
    print("yes")
else
    print("no")

Ko'rib turganingizdek, bu kodni birinchi qismida taxminan \(n^2\) ta amal, ikkinchi qismida \(3n\) ta amal va oxirgi qismida, \(3-4\) ta amal, aniqrog'i o'zgarmas miqdordagi amallar bajarilmoqda. Demak formulani, masalan \(n^2+3n+4\) desak bo'ladk.

Bunda javob esa, \(O(n^2)\). Avvalroq, o'rganganimizdek, o'sish sur'atiga eng katta had, ya'ni \(n^2\) asosiy ta'sir ko'rsatadi. Undan keyingi \(3*n+4\) esa \(n^2\) hadga faqat yig'indi bo'lib qo'shilgani uchun, o'sish sur'atiga ta'siri kam. Agar uchinchi for sikli ham yuqoridagi ikkita sikl bilan ichima ich joylashganida, murakkablik \(O(n^3)\) bo'lishi mumkin edi.

big_o

Ko'rishingiz mumkinki \(n\) ni qiymati oshgani sari, \(n^2+3n+4\) ham \(n^2\) bilan deyarli bir xil chiziqda bormoqda. Bunga \(3n+4\)ning ta'siri kamayib borishi sabab bo'ladi.

for(i = 1; i <= n; i ++)
for(j = 1; j <= m; j ++)
    sum += a[i] * b[j]

Bir qarashda ikkita sikl bo'lgani uchun \(O(n^2)\) deyish mumkin. Lekin, ikkinchi siklda m ishlatilgan. Demak, amallar soni ham \(O(nm)\) bo'ladi.

Bu holatda, \(O(nm)\) ni soddalashtirib \(O(n^2)\) deb yozish xato! Chunki \(m\) va \(n\) alohida o'zgaruvchilar. Ular o'sish sur'atiga bir xilda ta'sir ko'rsatishadi.

for(i = 1; i <= n; i ++)
    sum_a += a[i]

for(i = 1; i <= m; i ++)
    sum_b += b[i]

Xuddi shu kabi bu yerda ham ishlash vaqti \(O(n + m)\). Buni ham soddalashtirib, \(O(n)\) yoki \(O(m)\) deb yozish xato. \(n\) va \(m\) ni qiymatlari bir biridan mustasno va ishlash vaqtiga turlicha ta'sir o'tkazadi.

Shu bilan bir nechta oddiy misollarni ko'rib chiqdik. Albatta algoritmlar faqat for sikllaridan iborat bo'lmaydi, murakkabroq algoritmlarni baholashni o'rganish uchun esa faqat ko'proq mashq qilish lozim!

Nega \(\Theta\) emas \(O\)

E'tibor qilgan bo'lsangiz, \(\Theta\) notation algoritm o'sishini yuqori aniqlikda ifodalaydi va qaysidir ma'noda \(O\) notationdan ko'ra aniqroq deyishimiz mumkin.

Lekin dasturlashda \(\Theta\) notation deyarli ishlatilmaydi, asosan \(O\) dan foydalaniladi.

Buning ko'p sabablari bor. Eng birinchisi, \(O\) ni topish \(\Theta\)ni topishdan ko'ra ancha soddaroq bo'ladi. \(O\) notation aniq ishlash vaqtini emas, unga upper boundni ifodalagani uchun, uni hisoblash jarayoni ancha oson kechadi.

Ikkinchidan, \(O\) notationi yuqorida ta'riflangan eng yomon holat uchun ishlatish qulay, \(O\) notation o'zi aynan shu eng yomon holatni bildiradi. Biror algoritm \(O(n^2)\) deganimiz, algoritm eng yomon holatda \(n^2\) vaqtda ishlashini bildiradi.

Adabiyotlar

Algoritmlarni va masala ishlashni shoshmasdan, qanoat qilib o'rganmoqchi bo'lganlar uchun MIT professorlarining mashhur kitobi, "Introduction to Algorithms"ni o'qishni maslahat beraman. Algoritmlar va Ma'lumotlar tuzilmasiga oid tushunchalarni fundamental ravishda, to'liq o'rganishingiz mumkin.

Bu blogning ham ko'p qismi aynan shu kitobga asoslangan. Ammo, osonroq bo'lishi uchun ko'p muhim qismlarini qoldirib ketishimga to'g'ri keldi. Bu tushunchalarni mustaqil o'rganishni va kitobni 2- va 3- boblarini o'qib chiqishni maslahat beraman.

¹ Introduction to Algorithms, Fourth Edition Thomas H. Cormen;Charles E. Leiserson;Ronald L. Rivest;Clifford Stein;

² http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/index.html

Bundan keyin..

Keyingi qismda, xotira sarfini o'lchash va rekursiv algoritmlarni samaradorligini o'lchash haqida gaplashamiz.