Algoritm tushunchasi. Algoritimning intuitiv, formal va kibernetik ta`riflari,xossalari xamda ularning turlari

7.2.Izlash masalasi uchun algoritmlar.
Chiziqli qidiruv.

• 
  Aytaylik bizga massiv berilgan:
  
• 
  A={1,2,3,4,5,6,7,8,9,10}
  
• 
  Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan algoritm tuzish sharti qo'yilgan.
  
• 
  Ushbu masalani yechishda eng birinchi hayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
  
• 
  Chiziqli qidiruv - Linear Search deb ataladi, va bu usul algoritmi quyidagi ko'rinishda:
  

Blok-sxemasi:
Boshlash
N,A[N], X
i=1,..,N / A[i]≠X
1:Tamom
Yo’q 1

+/- Bor
Binar(ikkilik) qidiruv.

• 
  Bu usul binar qidiruvni iterativ usuli deyiladi, shuningdek bu algoritmni rekursiya usulida ham yozish mumkin, rekursiv usulni erinmasangiz o'zingiz yozib ko'ring. Bitta urinishda ko'pchilik dasturchilar bu narsani to'g'ri yoza olishmaydi va bu normal holat, chunki xato bor joyda o'z ustida ishlash uchun imkoniyat bo'ladi.
  

• 
  Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz:
  
• 
  funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish(kamayish) tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q
  
• 
  chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n).
  

10.2. Murakkablik ko’rsatkichini aniqlash
Algoritmlarning murakkabligi odatda bajarilish vaqti yoki foydalanilgan xotiraga qarab baholanadi. Ikkala holatda ham murakkablik kiritilgan ma'lumotlarning hajmiga bog'liq: 100 ta elementdan iborat massiv 1000 ta o'xshashiga qaraganda tezroq qayta ishlanadi. Shu bilan birga, kam odam aniq vaqt haqida qayg'uradi: bu protsessorga bog'liq, ma'lumotlar turi, dasturlash tili va boshqa ko'plab parametrlar. Faqat asimptotik murakkablik muhim, ya'ni kirishning o'lchami cheksizlikka moyil bo'lganligi sababli murakkablik.


Aytaylik, ba'zi bir algoritm n ta kiritilgan ma'lumotlar elementini qayta ishlash uchun 4n 3 + 7n shartli operatsiyalarni bajarishi kerak. n ortishi bilan umumiy ish vaqti n ni kubga ko'tarish uni 4 ga ko'paytirish yoki 7n qo'shishdan ko'ra sezilarli darajada ko'proq ta'sir qiladi. Keyin biz aytamizki, bu algoritmning vaqt murakkabligi O(n 3) ga teng, ya'ni u kiritilgan ma'lumotlarning hajmiga kubik bog'liq.


O kapitalidan foydalanish (yoki O-notatsiyasi deb ataladigan) matematikadan kelib chiqadi, bu erda u funktsiyalarning asimptotik xatti-harakatlarini solishtirish uchun ishlatiladi. Rasmiy ravishda O(f(n)) algoritmning ishlash vaqti (yoki band boʻlgan xotira miqdori) kiritilgan maʼlumotlar miqdoriga qarab f(n) ga koʻpaytiriladigan baʼzi bir doimiydan tezroq oʻsishini bildiradi