Reja: Algoritm tushunchasi va ular haqida ma’lumotlar

Algoritm va algoritmlar samaradorligini baholash

Reja:

• 1. Algoritm tushunchasi va ular haqida ma’lumotlar.
• 2. Algoritm xossalari turlari va uning berilish usullari.
• 3. Algoritmlarning murakkablik darajasi

Algoritm tushunchasi va ular haqida ma’lumotlar.
Ta’rif. Algoritm deb, qo‘yilgan masalani echish uchun ma’lum qoidaga binoan bajariladigan amallarning chekli qadamlar ketma-ketligiga aytiladi. Har qanday algoritm ma’lum ko‘rsatmalarga binoan bajariladi va bu ko‘rsatmalarga buyruq deyiladi.

Algoritm xossalari turlari va uning berilish usullari

• Algoritmning xossalari
• 1-xossa. Diskretlilik
• 2-xossa. Tushunarlilik
• 3-xossa. Aniqlilik
• 4-xossa. Ommaviylik
• 5-xossa. Natijaviylik

Algoritm xossalari turlari va uning berilish usullari
Algoritm xossalari turlari va uning berilish usullari
Algoritm samaradorligi deganda algoritmning berilgan masalani hal qilish uchun vaqt va xotira kabi hisoblash resurslaridan samarali foydalanish qobiliyati tushuniladi. Ko'pincha vaqt murakkabligi va hajm murakkabligi nuqtai nazaridan o'lchanadi.
Vaqt murakkabligi: Vaqt murakkabligi algoritmning kirish hajmiga bog'liq ishlashi uchun zarur bo'lgan vaqt miqdorini tavsiflaydi. Bu bizga algoritmni bajarish vaqti kattaroq ma'lumotlar to'plamlari bilan qanday o'sishini tushunishga yordam beradi. Vaqt murakkabligini ifodalash uchun ishlatiladigan umumiy belgilarga Big O notatsiyasi, Omega yozuvi va Teta yozuvi kiradi.
Hajm(xotira) murakkablik: hajm murakkablik algoritmga muammoni hal qilish uchun kerak bo'lgan xotira miqdorini aniqlaydi. U algoritmning xotiradan foydalanish hajmini kiritish hajmi bilan qanday o'lchashini o'lchaydi. Vaqt murakkabligi kabi, fazoning murakkabligi ham Big O belgisi yordamida ifodalanadi
Algoritmlarning murakkablik darajasi

Doimiy(oʻzgarmas) – O(c) (O(1)) Chiziqli – O(n) Kvadrat – O(n2) Kub – O(n3)

Eksponensial – (2n) Logarifmik – O(log(n)) Logarifmik chiziqli – O(nlog(n))

Quyida eng keng tarqalgan Katta-O(Big-O )funksiyalari keltirilgan:
Turli xil algoritmlarning murakkabligini tahlil qilish va qoʻyilgan masalani yechish uchun eng samarali algoritmni topish uchun katta O yozuvi (Big-O) algoritmning murakkabligini tavsiflash uchun ishlatiladigan statistik oʻlchovlardan foydalaniladi.
Algoritmlarning murakkablik darajasi
Doimiy murakkablik - O(C): Agar algoritmning bajarilishini yakunlash uchun zarur boʻlgan qadamlar kiritilgan ma’lumotlar sonidan qat’iy nazar, doimiy boʻlib qolsa, algoritmning murakkabligi doimiy deyiladi.
Doimiy murakkablik O(c) bilan belgilanadi, bunda c har qanday doimiy son boʻlishi mumkin.
Algoritmlarning murakkablik darajasi
Chiziqli murakkablik - O(n)
Algoritmning bajarilishini yakunlash uchun zarur boʻlgan bosqichlar kirishlar soniga qarab chiziqli ravishda ortib yoki kamaysa, algoritmning murakkabligi chiziqli deyiladi. Chiziqli murakkablik O(n) bilan belgilanadi.
Algoritmlarning murakkablik darajasi