Algoritm tushunchasi

Murakkablikni baholash. Algoritmlarning murakkabligi odatda
bajarilish vaqti yoki ishlatilgan xotira boʻyicha baholanadi. Ikkala
holatda ham, murakkablik kiritilgan ma’lumotlarning hajmiga bogʻliq:
100 ta elementdan iborat massivi xuddi shunga oʻxshash 1000 ta
elementdan iborat massivga qaraganda tezroq qayta ishlanadi. Faqatgina asimptotik murakkablik muhim, ya’ni kirish
ma’lumotlarining kattaligi cheksizlikka intilayotgandagi murakkablik.
Masalan, ba’zi bir algoritmga kirish ma’lumotlarining n ta
elementlarini qayta ishlash uchun 4n3 + 7n ta shartli amallarni bajarish
kerak. Ushbu algoritmning vaqt murakkabligi O(n3), ya’ni u kubik bilan
kiritilgan ma’lumotlarning hajmiga bogʻliq boʻladi.
Bosh harf O dan foydalanish matematikadan kelib chiqadi, bu yerda
ushbu belgi funksiyalarning asimptotik harakatlarini taqqoslash uchun
ishlatiladi. Rasmiy ravishda O(f(n)) algoritmning ishlash vaqti (yoki
egallagan xotira miqdori), kiritilgan ma’lumotlarning hajmiga qarab,
f(n) ga koʻpaytiriladigan ba’zi konstantalardan tezroq emasligini
anglatadi.
6 Chiziqli murakkablik, logarifmik murakkablik, kvadratik murakkablik
O (n) - chiziqli murakkablik. Bunday murakkablik, masalan,
saralanmagan massivdagi eng katta elementni topish algoritmiga ega.
Qaysi biri maksimal ekanligini aniqlash uchun massivning barcha n
elementlaridan oʻtishimiz kerak boʻladi.
O (log n) - logaritmik murakkablik. Eng oddiy misol - ikkilik
qidirish. Agar massiv saralangan boʻlsa, uni yarmiga boʻlish orqali
ma’lum bir qiymatga ega ekanligini tekshirishimiz mumkin. Oʻrta
elementni tekshirib koʻramiz, agar u kattaroq boʻlsa, unda massivning
ikkinchi yarmini tashlab yuboramiz. Agar kichikroq boʻlsa, unda
aksincha - biz dastlabki yarmini tashlaymiz va shu tarzda ikkiga
boʻlinishni davom ettiramiz, natijada (logn) elementlarini tekshiramiz.