1-Mustaqil ish. Mavzu: Chiziqli va tarmoqlanuvchi algoritmlar. Savollarga nazariy javob bering

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²) murakkablikdagi baholashlarni taqqoslang- 'o(n)' va 'o(n^2)' murakkablikdagi baholashlar algoritmlarning samaradorligini ifodalaydi.

'o(n)' murakkablikdagi algoritm, ma'lum bir ishni bajarganingizda bajarilgan amallar sonini ifodalaydi. Boshqa so'zlar bilan aytganda, agarda 'n' elementdan iborat bir listaga yig'ilgan ma'lumotlarni qidiruvchi dasturda 'n' marta ishlatilgan amallar soni 'n' ga teng bo'ladi.

'o(n^2)' murakkablikdagi algoritm esa, har bir yozuvning har bir boshqa yozuvga mosholasi bilan ishlovchi algoritm turi hisoblanadi. Boshqa so'zlar bilan aytganda, agarda 'n' elementdan iborat bir listaga yig'ilgan ma'lumotlarni qidiruvchi dasturda, dasturda 'n' marta amallar ishlatilsa, unda ishlatilgan barcha amallar soni 'n^2' ga teng bo'ladi.

Bundan tashqari, 'o(n^2)' murakkablikdagi algoritmlar o'sishi osonmasligi va ishlab chiqish jarayonlari kabi sabablar bilan bir necha elchinish joylarida talab qilinmaydi. Bunday holatda so'rov uchun qandaydir boshqa tanlovlar yoki yanada qisqa va samarali bo'lgan muharrirning ushbu talablari axvolini tekshirish kerak.

4.