2 мustaqil ta’lim ish hisoboti Fan “ Algoritmlarni loyihalash” Fan o’qituvchisi: Bobonazarov A. Talaba: Erbo’tayev F

Ikkinchi nazariy savol javobi

Algoritmlarni asimptotik (O()) baholash – algoritmda kiruvchi ma’lumotlarning bajariladigan amallar soniga ma’lum bir qonuniyatlar asosida mos qo’yilishidir. Bu qonuniyatlar kvadratik, factorial, logarifmik bo’lishi mumkin.
Agar kiruvchi ma'lumotlarning o'lchamlari oshsa, algoritmning bajarilish vaqti f(N) funksiyasi bilan bir xil tezlikda oshsa, algoritmda O(f(n)) murakkablik bor.
Agar kiruvchi ma'lumotlarning o'lchamlari oshsa, algoritmning bajarilish vaqti f(N) funksiyasi kvadratik tezlikda oshsa, algoritmda O(f(n^2)) murakkablik bor.
Uch asimptotik belgilar asosan algoritmlarning vaqt murakkabligini ifodalash uchun ishlatiladi :

1. 
   Θ-notation ( teta );
   
2. 
   O-notation ( O );
   
3. 
   Ω notasi ( Omega ).
   

Hisoblash mashinalar tezligi oshishiga qaramasdan, ular yordamida yechilayotgan masalalar kattaligini oshishini algoritm qiyinligini tahlil orqali aniqlaydi.

3) uchinchi nazariy savol javobi
O(n) va O(n^2) murakkablikdagi baholashlarni taqqoslash uchun, biz murakkabliklarini tushunish, tahlil qilish va ularga misol topishimiz kerak.

O(n) murakkablikdagi algoritmlar(n esa murakkablik darajasini bildiradi) sonli sonlar katta yoki kichik bo'lsa ham barcha elementlarni ko'rib chiqishga qodirroq. Misol uchun, agar bizda bir massiv bo'lsa, n va k sonli elementlarga ega bo'lsa, O(n) murakkablikda biz barcha n elementlarini ovoriladi va ko'rib chiqishimiz mumkin.

O(n^2) murakkablikdagi algoritmlar esa, murakkablik darajasi kvadrat boylikdagi darajaga tengdir. Bu usuli ko'p elementli massivlarda qo'llaniladi va barcha elementlar orasida ikki ba'zi qiymatni taqqoslash bo'yicha ishlatiladi. Misol uchun, agar bizdar n sonli ikki massivimiz bo'lsa, biz ularning har bir elementini olib, ularni hisoblash uchun murakkab ko'pchilik, bundan keyin esa har bir elementni ichidagi massiv bilan taqqoslaymiz, shuningdek, massivni boshidan o'ziga qarab k, k dan boshlab oxiriga qarab n ta elementni ko'rib chiqishni qo'llaymiz. Bunday murakkablikka kirish mumkin, shuning uchun O(n^2) ni murakkablik darajasi katta matematikamizda siklga to'g'ri keladi.