Algoritmni to’liq qurish bosqichlari bilan quyida tanishib chiqamiz:
Masalaning qo’yilishi
Modelni qurish
Algoritmni ishlab chiqish
Algoritm to’g’riligini tekshirish
Kodlashtirish
Dasturni tekshirish
Hujjatlashtirish
Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq.
Albatta, algoritmni aniq sxema bo’yicha tuzish zarur bo’lib qoladigan sodda hollar ham mavjud. Bunday hollarda yechilish algoritmi avval biron kim tomonidan olingan masalalarni misol keltirish mumkin. Masalan, differensial tenglamalarni sonli integrallash uchun Eyler metodi. Bu metod masalani yechish uchun umumiy holda ifodalangan algoritmdir.
Algoritmlar sifatini baholash uchun mezonlarni ko’raylik. Mavjud mezonlar juda taxminlashgan. Masalan, algoritmni bajarishda bajaruvchining xotira uskunalari hajmi yetarli bo’lmasa, u algoritm yomon deb hisoblanadi. Boshqa mezon sifatida algoritmning bajarilishi uchun talab qilinadigan vaqtni ko’rsatish mumkin. Vaqtni baholash bajaruvchining fizik xarakteristikalari hisobga olinishi kerak. Chunki har bir operatsiya har xil o’zgaruvchilar bilan bajarilganda vaqt ham har xil bo’ladi. Bunchalik aniq ma’lumotni har bir foydalanuvchi uchun yig’ib bo’lmaganligi sababli odatda o’rtacha tezkorlik qabul qilinadi. Ketma-ket bajarilayotgan operatsiyalar sonini aniqlab, uni o’rtacha tezkorlikka ko’paytirsa, algoritm bajarilishining amalga yaqin bo’lgan vaqtini topishimiz mumkin.
Demak, algoritmlarni baholash uchun ikkita asosiy kretiriya mavjud ekan.
Algoritmni ishlash vaqti bo’yicha baholash
Algoritmni bajarish uchun xotiradan egallagan hajmi bo’yicha baholash
Algoritmlarni hajmiy (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.
Faraz qilaylik, A1,A2,…,A5 nomli 5 ta algoritm quyidagi vaqtli qiyinliklar bilan berilgan.
Algoritm
|
Vaqtli qiyinlik
|
A1
|
N
|
A2
|
N log2 n
|
A3
|
N 2
|
A4
|
N 3
|
A5
|
2n
|
Bu yerda vaqtli qiyinlik – bu n kattalikdagi kirishlarni qayta ishlash uchun kerak bo’ladigan vaqt birliklar soni. Masalan, vaqt birligini 1 millisekund deb qabul qilaylik.
Bunda A1 algoritm bir sekundda 1000 kattalikdagi kirishni qayta ishlash mumkin, A5 algoritmi esa kirish kattalikdagina 9 dan oshirib bilmaydi.
Keyingi jadval 1 sekundda, 1 minutda, 1 soatda 5 ta algoritmlarni har birining yordamida yechiladigan masalaning kattaligi keltirilgan.
Algoritm
|
Vaqtli qiyinlik
|
Masalaning maksimal o’lchami
|
1 sek
|
1 min
|
1 soat
|
A1
|
N
|
1000
|
60*100
|
3,6 *106
|
A2
|
N log2 n
|
140
|
4893
|
2 *104
|
A3
|
N 2
|
31
|
244
|
1897
|
A4
|
N 3
|
10
|
39
|
153
|
A5
|
2n
|
9
|
15
|
21
|
“O-yozuv” usulning kamchiligi shundaki – konkret berilganlar uchun dastur bajarilishiga aniq sarflanayotgan vaqtni hisoblab bilmaymiz, faqatgina qadamlar
bajarilish soni
O(n )
bo’lganini bildik. Lekin bu usul bilan tahlil qilish qulay, va
berilgan amaliy masala uchun dasturni samaradorligini aniqlaydigan dastlabki hisoblashlar uchun algoritmning isahlash vaqtini assimptotik bahosini beradi.
Samaradorlikni baholashga misollar
Masala, Qalam va qog’oz yordamida, quyidagi 16 ta kvadratdan iborat shaklni yasash kerak.
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
Algoritm bahosi O(n)
Bu jarayon 4 ta qadamda bajarildi. Demak algoritm bahosi O(logN)
Agar biz dasturimizda bir o’lchovli massivdan foydalansak, bu kamida O(n) bilan baholanadi.
Masala. Bir o’lchovli massivning elementlarini 2 ga ko’paytirish algoritmini baholang
for(int i=0; i>a[i];
for(int i=0; i
Bu yerda sikl operatori (for(int i=0; iMasala. Ikki o’lchovli massivning elementlarini 2 ga ko’paytirish algoritmni baholang.
for(int i=0; i{
a[i][j]*=2;
}
Bu algoritmning matematik modeli
𝑛−1 𝑛−1
𝑛−1
𝑛−1
𝑆(𝑛) = ∑ ∑ 1 = ∑ 1˛_+_1_…_. +¸1 = ∑ 𝑛 = (1˛_+_1_+ ⋯_+_¸1) 𝑛 = 𝑛𝑛 = 𝑛2
𝑖=0 j=0
𝑖=0 𝑛
𝑖=0
|
