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 :
Θ-notation ( teta );
O-notation ( O );
Ω notasi ( Omega ).
Hisoblash mashinalar tezligi oshishiga qaramasdan, ular yordamida yechilayotgan masalalar kattaligini oshishini algoritm qiyinligini tahlil orqali aniqlaydi.
3) Uchinchi nazariy savol javobi
Algoritmning murakkabligi ni nazorat qilish uchun O(n) va O(n^2) murakkabliklarga qaraganda taqqoslash odatiydir.
1. **O(n) murakkablik**: Bu murakkablik darajasi algoritmlarda bajarilgan amallarning miqdori tomonidan ifodalangan. Agar algoritmda bir marta to'lov bajarilsa, bu O(n) murakkablikka misol bo'ladi. Misol uchun, bir massivdagi barcha elementlarni yig'indisi O(n) murakkablikka ega bo'ladi, chunki barcha elementlar yagona marta ko'riladi.
2. **O(n^2) murakkablik**: Bu murakkablik darajasi algoritmlar uchun ikki marta to'lov bajarilishi mumkin bo'lgan amallarning miqdori tomonidan ifodalangan. Misol uchun, bitta massivdagi barcha elementlarni boshqa barcha elementlar bilan solishtirish uchun chetlab qo'yganda, bu O(n^2) murakkablikka ega bo'ladi. Chunki har bir element barcha qolgan elementlar bilan solishtiriladi.
Agar boshqalar O(n^2) murakkablikdan O(n) murakkablikka o'tkazilgan algoritmni yaratish mumkin bo'lsa, bu odatda samarali vaqt shaklida ishlashning olinishi uchun qobiliyatga ega bo'ladigan muhim qadam hisoblanadi.
|
