manba

Sodda amallarning asimptotik analizi

Sodda amallarning asimptotik analizi

O'tgan galgi maqolarimizda asimptotik analiz, eng yaxshi,o'rta va eng yomon holatlar va asimptotik notatsiya haqida so'z borgan edi. Bugungi maqolada sodda amallarning vaqt murakkabligi muhokama qilinadi.

1. O(1). Rekursiv va iterativ bo'lmagan har qanday ifodalarning vaqt murakkabligini ifodalaydi.

/*Ushbu funksiya ichida yotgan barcha amallaring vaqt murakkabligi O(1) ga teng.*/
        public void EngKattaSon()
        {
            int a = 10;   //O(1)
            int b = 20;  //O(1)
            int c = 30;  //O(1)
            if (a > b && a > c) //O(1)
                Console.WriteLine("a eng katta son"); //O(1)
            else if (b > c) //\(O(1)\)
                Console.WriteLine("b eng katta son"); //O(1)
            else //\(O(1)\)
                Console.WriteLine("c eng katta son"); //O(1)

            for (int i = 0; i < 3; i++)
            {
                Console.WriteLine("agar iteratsiya konstant marta(bu holatda 3 marta) qaytarilsa, bu holatdayam O(1) sifatida qaraladi");//O(1)
            }
        }

2. O(n). Agar iteratsiya qandaydir c ga o'sib/kamayib borsa bunday iterativ ifodaning vaqt murakkabligi O(n)ga teng bo'ladi. Quyida berilgan ifoda bunga misol bo'ladi.

/* bu yerda c musbat integer raqam.*/
   for (int i = 1; i <= n; i += c)
   {
     // ixtiyoriy O(1) ifoda
   }

   for (int i = n; i > 0; i -= c)
   {
     // ixtiyoriy O(1) ifoda
   }

3. O(n^t). Agar funksiya tarkibida ichma-ich joylashgan iterativ ifoda mavjud bo'lsa u holda uning vaqtga bo'lgan talabi O(n^t)ga teng. Masalan quyida berilgan kod parchasining talabi O(n^2)ga teng.

for (int i = 1; i <= n; i += c)
 {
   for (int j = 1; j <= n; j += c)
   {
     // ixtiyoriy O(1) ifoda
   }
 }

 for (int i = n; i > 0; i += c)
 {
  for (int j = i + 1; j <= n; j += c)
  {
   // ixtiyoriy O(1) ifoda
  }
 }

4. O(logn). Agar iterativ ifoda c konstanta marta ko'payib/kamayib borsa u holda bunday ifodaning vaqt murakkabligi O(logn)ga teng bo'ladi.

for (int i = 1; i <= n; i *= c)
  {
     // ixtiyoriy O(1) ifoda
  }
  for (int i = n; i > 0; i /= c)
  {
   // ixtiyoriy O(1) ifoda
  }

Masalan, ikkilik qidiruv ushbu murakkablikka ega.

5. O(loglogn). Agar iterativ ifoda c konstanta qiymatda eksponsial ko'rinishda o'sib/kamayib borsa u holda bu ifodaning vaqt murakkabligi O(loglogn)ga teng.

/*c ning qiymati birdan 1 dan yuqori*/ 
 for (int i = 1; i <= n; i = pow(i,c))
  {
     // ixtiyoriy O(1) ifoda
  }

 /*bu yerda fun bu qandaydur ildizdan chiqarish funksiyasi*/ 
  for (int i = n; i > 0; i = fun(i,c))
  {
   // ixtiyoriy O(1) ifoda
  }

Agar funksiya tarkibida mos ravishda va gacha o'sib/kamayib boradigan iterativ ifoda bo'lsa nima qilamiz?

for (int i = 1; i <= m; i += c)
 {
   // ixtiyoriy O(1) ifoda
 }
for (int i = 1; i <= n; i += c)
 {
    // ixtiyoriy O(1) ifoda
 }

Yuqorida berilgan kod parchasining murakkabligi O(m) + (n)=O(m + n) ga teng bo'ladi. Agar m == n bo'lsa murakkablik O(2n)ga aylanadi bu esa o'z navbatida O(n)ga teng.

Manba:


JONNY - Texnoman foydalanuvchisi

Muallif haqida

JONNY Arduino, Java, C#, Android, Windows, Linux, Debian, Javascript. O'zbekistonni rivojlantiramiz! Dasturlash orqali vatanimizni yangi marralarga olib chiqamiz.


Blogdagi so‘nggi maqolalar:


Birinchi bo‘ling!

Iltimos, fikr bildirish uchun saytga kiring yoki ro‘yxatdan o‘ting!