Va kommunikatsiyalarni rivojlantirish vazirligi

Birlashmali saralashning boshqa saralash algoritmlari bilan solishtirish:
Algoritm Eng yaxshi O`rtacha Engyomon
Tanlab saralash O(n^2) O(n^2) O(n^2)
Pufakchali saralash O(n) O(n^2) O(n^2)
Tezkor saralash O(n log(n)) O(n log(n)) O(n^2)
Birlashmali saralash O(n log(n)) O(n log(n)) O(n log(n))
Jadvaldan ko`rinib turibdiki, umumiy holatda birlashmali saralash algoritmidan foydalanish samaraliroq hisoblanadi.
Nazorat savollari

1. 
   Jarayon matematik modelini tuzishda eng kichik kvadratlar usulidan foydalanish algoritmini tahlil qiling.
   
2. 
   Jarayon matematik modelini tuzishda eng kichik kvadratlar usulidan foydalanish qanday amalga oshirilishini tahlil qiling.
   

LABORATORIYA ISHI - 18
Mavzu: Kvadratik, teskari proporsional bog’lanish modellari.
Ishdan maqsad. Kvadratik, teskari proporsional bog’lanish modellarini o’rganish.
Qo’yilgan masala. Kvadratik, teskari proporsional bog’lanish modellari.
Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o‘rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

Nazariy qism
Eng yaqin nuqtalar juftligi topish vazifasi hisoblash geometriyasi vazifasidir. Misol uchun metrik bo'shliqda n nuqtalari berilgan, ular orasidagi eng kichik masofa bo'lgan bir necha nuqtani topish masalasini ko’rib chiqaylik. Evklid tekisligidagi eng yaqin nuqtalarning vazifasi geometrik algoritmlarning hisoblash murakkabligidan muntazam ravishda o'rganilishi kerak bo'lgan birinchi geometrik vazifalardan biri edi.

Barcha juftliklar orasidagi masofani topish uchun sodda algoritm d o'lchamlari va ular orasida eng kam tanlash O ( n 2) vaqt talab qiladi. Bu muammo Evklid kosmosda yoki sobit hajmi D l p kosmosda vaqtida hal qilinishi mumkin ekan. Algebraik yechim daraxtini hisoblash modelida vaqt bilan algoritm elementning o'ziga xosligi muammosini kamaytirish foydalanish qulay.. Hisoblash modeli qabul qilingan funktsiya - doimiy vaqt uchun hisoblab chiqilgan, vazifa vaqtida hal qilinishi mumkin . Agar biz randomizatsiyani zamin funktsiyasi bilan birga qo'llasak, muammoni O(n) vaqtida hal qilish mumkin.
Eng yaqin nuqta juftligi O ( n 2) vaqtida to'liq qidirish orqali hisoblanishi mumkin. Buni amalga oshirish uchun barcha n ( n − 1) / 2 juft nuqtalari orasidagi masofani hisoblash mumkin, keyin quyida ko'rsatilganidek, eng kichik masofa bilan juftlikni tanlang.
minDist = infinity