Samarqand davlat universiteti raqamli texnologiyalar fakulteti dasturiy injiniring yo

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

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

Saralash algoritmlari
Saralash algoritmlari – informatikada juda yaxshi o’rganilgan sohalardan biri va u juda keng qamrovli qo’llanilish sohasiga ega. Ularni katta hajmdagi ma’lumotlarni saqlash va qayta ishlash amallari bajariladigan har qanday joyda uchratish mimkin. Ba’zi ma’lumotlarni qayta ishlash masalalari agar ma’lumotlar saralangan bo’lsa oson yechiladi. Bunday masalalar ushbu laboratoriya ishida ko’rib chiqiladi.