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 

	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  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  0; i += c)
 {
  for (int j = i + 1; j 

	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  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  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 

	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: 
               
                Ulug'bek Normatov