Laboratoriya ishi №1. Ma’lumotlarni saralash algoritmlarining murakkabligini tahlil qilish. Ustuvor navbatlar

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n²)

3. 
   O(f/g)=O(f)/O(g) – ikkita funksiyaning bo’linmasining murakkabligi ular murakkabliklarining bo’linmasiga teng, masalan:
   

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

4. 
   O(f+g) teng O(f) va O(g) larning dominantiga – funksiyalar summasining murakkabligini baholash, birinchi va ikkinchi qo’shiluvchilarning dominant (hukmron) murakkabligini baholash bilan belgilanadi, masalan:
   

O(n⁵+n¹⁰) = O(n¹⁰)

Amallarning sonini sanash juda mayda ish, eng muhimi bu unchalik muhim emas. Yuqorida keltirilgan qoidalardan kelib chiqqan holda, algoritmning murakkabligini aniqlashda oldin bajarganimizdek amallarni sanash kerak emas, biz uchun algoritm (operator yoki operatorlar guruhi) konstruksiyasi qaysi murakkablik darajasiga mansubligini bilish kifoya. Bundan ma’lumki, sikl va rekursiyalarga ega bo’lmagan algoritm O(1) konstanta murakkabligiga ega. n ta iteratsiyani bajaruvchi siklning murakkabligi O(n) ga teng. Bitta n o’zgaruvchi qiymatiga bog’liq bo’lgan ichma ich joylashgan ikkita siklning konstruksiyasi kvadratik murakkablikka O(n²) ega bo’ladi.

Quyida eng ko’p uchraydigan murakkablik sinflari keltirilgan:

• 
  O(1) – konstantali murakkablik;
  
• 
  О(n) – chiziqli murakkablik;
  
• 
  О(n^а) – polynomial murakkablik;
  
• 
  О(log(n)) – logarifmik murakkablik;
  
• 
  O(n*log(n)) – kvazichiziqli murakkablik;
  
• 
  O(2ⁿ) – eksponensial murakkablik;
  
• 
  O(n!) –factorial murakkablik.