Mustaqil ish ­­ cal015 (415) guruh talabasi Bajardi: Nabijonov Hamidjon Tekshirdi: Begimov O’ktam

Big-O belgilari nima?

• 
  Nazariy jihatdan Big - O belgisi algoritmning ishlashi/murakkabligini tekshirish uchun ishlatiladi. 
  
• 
  Big – O belgisi algoritmning ishlashning yuqori chegarasini, ya’ni uning eng yomon holatdagi harakatini tekshiradi. 
  
• 
  Big –O belgisi, shuningdek, asimptotik algoritm xatti-harakatlarini ham ko'rib chiqadi, bu kirish miqdori juda katta bo'lganida usulning ishlashiga ishora qiladi. 
  
• 
  Hisoblash murakkabligi asimptoti O(f) kiritilgan ma'lumotlarning (CPU vaqti, RAM va boshqalar) kattaligiga asoslangan holda foydalaniladigan resurslar tartibini o'lchaydi.
  

Turli xil vaqt murakkabliklari

Vaqt murakkabligi holatlarining besh turi mavjud:

1. 
   Doimiy vaqt murakkabligi - O(1)
   
2. 
   Logarifmik vaqt murakkabligi - O(log n)
   
3. 
   Chiziqli vaqt murakkabligi - O(n)
   
4. 
   O(n log n) Vaqt murakkabligi
   
5. 
   Kvadrat vaqt murakkabligi - O(n2)
   

Endi bularni batafsil ko'rib chiqing.

Doimiy vaqt murakkabligi - O(1)

Agar usulning vaqti o'zgarmasa va kirish hajmi kattalashganda doimiy bo'lib qolsa, algoritm O (1) murakkabligiga ega deyiladi. Algoritmga kirish hajmi ta'sir qilmaydi. Muayyan operatsiyani bajarish uchun ma'lum miqdordagi qadamlar kerak bo'ladi va bu raqam kiritilgan ma'lumotlarning miqdoriga bog'liq emas.
Code:
using System;
namespace DSAComplexity
{
class Program
{
static void ConstantTimeComplexity()
{
int a = 100;
int b = 50;
int sum = a + b;
Console.WriteLine(sum);
}
static void Main(string[] args)
{
ConstantTimeComplexity();
}
}
Bu Constant Time Complexity dasturini amalga oshirish edi. Keyin siz O(log n) Vaqt murakkabligini ko'rasiz.

Logarifmik vaqt murakkabligi - O(log n)

Logarifmik murakkablikdagi usul (bu erda n haqiqatan ham katta) masalani har bir iteratsiya uchun kichik bitlarga ajratadi (log n). Logarifm asosi odatda 2 ga teng bo'lgan N ta elementda ma'lum bir amalni bajarish uchun log(N) qadamlar kerak. Logarifm bazasi amallarni hisoblash tartibi uchun muhim bo'lmagani uchun u ko'pincha e'tiborga olinmaydi.
Code:
// C# implementation of iterative Binary Search
using System;
namespace DSAComplexity{
class program {
//This will return index of x if it is present in arr[],
// else return -1
static int binarySearch(int[] arr, int x)
{
int l = 0, r = arr.Length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
/ Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
// Driver method to test above
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int n = arr.Length;
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
Console.WriteLine("Element not present");
else
Console.WriteLine("Element found at " +"index " + result);
}
}
}