for all 256 simvol do
hisobchiga nol qiymatni o‘zlashtirish
end for
while faylda tekshirilmagan simvollar bor do
keyingi simvolni kiritish
o‘qilgan simvol soni hisobchisini bittaga oshirish
end while
Algoritm ishini ko„rib o„taylik: bunda u initsializatsiya siklida 256 ta o„tishni amalga
oshiradi. Agar faylda N ta simvol bo„lsa, for siklida sikl o„zgaruvchisi initsializatsiya qilinib,
so„ngra o„zgaruvchining sikl doirasidan chiqmaganligi tekshiriladi va qiymati bittaga oshiriladi.
Bundan initsializatsiya siklida 257 ta (bitta sikl o„zgaruvchisi uchun, 256 ta sikl
o„zgaruvchisining orttirilishi uchun) o„zlashtirish hamda 257 ta (o„zgaruvchining sikl doirasidan
chiqib ketmaganligini tekshirish va bitta siklni to„xtatish uchun) tekshirish amali bajarilishi kelib
chiqadi. Ikkinchi siklda N + 1 (+1 fayl bo„shagandan keyingi oxirgi tekshirish) marta shart
tekshirish va hisobchini N marta o„stirish bajariladi. Hamamsi bo„lib amallar soni quyidagicha:
o„stirishlar soni N+256 ta ; o„zlashtirishlar soni 257 ta; shartlarni tekshirishlar soni N + 258 ga
teng. Shunday qilib, 500 simvollik faylni qayta ishlovchi algoritm 1771 ta amal bajaradi. Bundan
770 (43%) tasi initializatsiyaga tegishli. Agar fayl 50 000 ta simvolni o„zida saqlasa, algoritm
100 771 amalni bajarib, bulardan 770(1% dan kamroq) initsializatsiyaga tegishli bo„ladi.
Initsializatsiya jarayoni algoritmning vaqt bo„yicha ko„rsatkichlariga aytarli ta‟sir ko„rsatmaydi.
Boshlang„ich berilganlar sinflari
Algoritmlar tahlili jarayonida boshlang„ich kirish ma‟lumotlarining ahamiyati kattadir. Chunki
algoritmning bajarilish ketma-ketligi to„g„ridan-to„g„ri boshlang„ich berilganlarga bog„liq
bo„ladi.Masalan, N ta elementdan iborat ro„yxatdan eng kattasini topish uchun quyidagi
algoritmldan foydalanish mukin:
largest = list [1]
fori=2 toN do
if (list [i] > largest) then
largest = list [i]
end if
end for
Agar berilgan ro„yxat kamayib borish tartibida saralangan bo„lsa, sikl oldidan bitta
o„zlashtirish amali bajarilib, sikl tanasida o„zlashtirishlar bajarilmaydi.Agar ro„yxat o„sib borish
tartibida saralangan bo„lsa, hammasi bo„lib, N ta o„zlashtirish (bitta sikl oldidan va N -1ta sikl
ichida) amali bajariladi. Tahlil jarayonida boshlang„ich berilganlarning turli mukin bo„lgan
to„plamlari ko„rib o„tiladi. Bunda berilganlar to„plamlari sinflarga bo„linib o„rganiladi. Masalan,
10 ta sondan iborat ro„yxatdagi joylashtirishlar soni 3 628 800 ga teng.Ushbu sonli ro„yxatga
eng katta elementni izlash algoritmini qo„llayiz. Bunda boshlang„ich berilganlarning birinchi
elementi eng katta bo„lganlarining soni 362 880 ga teng.Ularning barchasini bir sinfga
birlashtirish mumkin.Eng katta element ikkinchi o„rinda turgan to„plamlar soni ham 362 880 ta.
Ularni boshqa sinfga birlashtirish mumkin. Bunda algoritmning bajarilish jarayonida amalga
oshiriladigan o„zlashtirish amallarining soni eng katta elementning ro„yxatda egallagan tartib
raqamiga teng bo„ladi. Shunday qilib, barcha boshlang„ich berilganlar to„plamlarini bajariladigan
o„zlashtirish amallari soniga qarab N ta turli sinfga ajratish mumkin.
Algoritmlar tahlilida boshlang„ich ma‟lumotlarni tanlash uning bajarilishiga sezilarli ta‟sir
ko„rsatadi.Jumladan, saralash algoritmlari boshlang„ich ketma-ketlik saralangan bo„lsa, juda tez
ishlagani holda, boshqa algoritmlar xuddi shu boshlang„ich berilganlar ustida ishlashning
o„rtacha natijasini ko„rsatadi. Shuning uchun algoritmlarning bitta boshlang„ich berilganlar
to„plami bilan ishlashini tahlil qilish emas, algoritmning eng tez ishini hamda yeng sekin ishini
ta‟minlovchi boshlang„ich berilganlar to„plamlarini izlash maqsad qilib qo„yiladi. Bundan
tashqari tekshiriluvchi algoritmning barcha mumkin bo„lgan boshlang„ich berilganlar
to„plalarida ko„rsatadigan natijalarining o„rtacha qiymatlari ham baholanadi.
Eng yaxshi holat Boshlang„ich berilganlarning algoritm bajarilishining minimal vaqtini
ta‟minlovchi to„plami eng yaxshi holatni bildiradi. Ushbu boshlang„ich berilganlar bilan
ishlaganda algoritm eng kam sondagi amallarni bajaradi.Agar masalan, izlash algoritmi
tekshirilayotgan bo„lsa, berilganlar to„plami eng yaxshi hisoblanadi, qachonki izlanayotgan
obyekt tekshiriluvchi yacheykalarning eng birinchisida joylashtirilgan bo„lsa
Eng yomon holat
Algorit ishining eng yomon holatini tahlil etish ham juda muhim ahamiyatga ega. Chunki bu
algoritm ishining umkin bo„lgan maksimal vaqtini aniqlash imkonini beradi. Eng yomon holatni
tahlil qilishda algoritm eng ko„p ish bajaruvchi boshlang„ich berilganlar to„plami izlanadi. Izlash
algoritmi uchun bunday berilganlar to„plami – bu izlangan element teshiriluvchi obyektlardan
eng oxirgisi bo„lgan yoki butunlay mavjud bo„lmagan ro„yxatdir. Eng yomon holat tahlili
algoritm ishlash vaqtining yuqori bahosini beradi.
O„rtacha holat
O„rtacha holat tahlili yeng murakkab bo„lib hisoblanadi, chunki bunda bir necha etapdan iborat
ish bajariladi. Birinchi qadamda mumkin bo„lgan boshlang„ich berilganlar guruxlari sinflarga
ajratiladi.Ikkinchi qadamda har bir berilganlar to„plamining sinflarga tegishli bo„lish ehtimoli
aniqlanadi. Keyingi qadamda xar bir sinfga tegishli berilganlar sinfi bilan ishlashda algoritmning
sarf qiladigan vaqti hisoblanadi. Ushbu vaqt bir sinfga tegishli berilganlar to„plamlari uchun bir
xil bo„lishi kerak. O„rtacha vaqt quyidagi formula bilan aniqlanadi:
( ) ∑
( )
Bu yerda n - boshlang„ich berilganlar xajmi, m – sinflar soni pi - berilganlar
to„plamining i nomerli sinfga tegishli bo„lish ehtimoli, ti - algoritmning i- sinfga tegishli
berilganlarni qayta ishlashga sarflaydigan vaqti.
Ba‟zi holatlarda berilganlar to„plamlarining sinflarga tegishli bo„lish ehtimoli bir-biriga
teng bo„ladi. Boshqacha aytganda, agar sinflar soni beshta bo„lsa, har bir sinfga tegishli bo„lish
ehtimoli 0,2 ga teng. Bunday holda algoritm ishining o„rtacha vaqtini yuqoridagi forula bilan
hisoblash yoki unga ekvivalent soddalashtirilgan formula bilan hisoblash mukin:
( )
∑
( )
Xotira bo„yicha murakkablik
Algoritmlar asosan sarf etadigan vaqti bo„yicha qiyoslansa ham,u yoki bu algoritmning
ishlashi uchun egallaydigan xotira xaji ham e‟tiborga molikdir. Kompyuterlar rivojining
boshlang„ich davrlarida xotira resurslarining yetishovchiligi sharoitida algoritmlarning
xotiratalablik bo„yicha tahlili prinsipial ahamiyatga ega edi. Ko„pgina holatlarda dasturchilar
sekinroq ishlaydigan, ammo qo„shimcha xotira talab qilmaydigan algoritmlarni tanlashga majbur
bo„lganlar.Xotira resurslariga talab juda katta bo„lganligidan qaysi ma‟lumotlar saqlanishi kerak,
saqlashning effektiv usullari?,- degan savol ham dolzarb hisoblangan. Hozirgi vaqtda ishlab
chiqarilayotgan dasturiy ta‟minotga qarab , xotira resurslarini iqtisod qilish usullariga yeralicha
e‟tibor berilmayotganligining guvohi bo„lamiz. Xatto juda sodda dasturlarning ishi uchun zarur
bo„lgan xotira xajmi megabaytlarda o„lchanadi. Dasturiy ta‟minot ishlab chiqaruvchilarini
xotirani iqtisod qilish muammosi endilikda qiziqtirmayotir.
O„sish tezligi
Algoritmlar tahlilida algoritm bajaradigan amallarning soni ahamiyatga ega bo„lmasdan,
ularning boshlang„ich berilganlar soni ortgandagi o„sish tezligi tekshiriladi. Ushbu kattalik
algoritmning o„sish tezligi deb ataladi.
Funksiyalar o„sish tezliklari grafiklari
O„sish tezliklari tasvirida to„rtta funksiyaning grafiklari keltirilgan. x2 funksiya oldin sekin
o„sadi, ammo x ning o„sib borishi bilan uning o„sish tezligi ham ortib boradi; x+10 va 3x-2
funksiyalarning o„sish tezligi o„zgarmasdan qoladi; 2 log x funksiya butunlay o„smayotgandek
ko„rinsada, u juda sekin tezlik bilan o„sadi.
Funksiyalar o„sish tezliklari jadvali
2-rasmda ba‟zi tez-tez uchrab turuvchi funksiyalarning o„sish tezligi o„z ifodasini topgan.
Rasmdan funksiyalarning qiymatlari kichik argumet naborlari uchun bir biridan kam farq
qilsada, ushbu naborlar xajmining o„sishi bilan bu farqlar ham o„sib boradi. 1- va 2-rasmlardagi
ma‟lumotlar funksiyalarning yana bir xususiyatini ifodalaydi. Bu xususiyatga ko„ra algoritmning
o„sish tezligini hisoblashda tez o„suvchan funksiyalar olinib, sekin o„suvchan funksiyalar
tashlab yuboriladi . Masalan, algoritmning o„sish tezligi x3-30x ifoda bilan hisoblansa, x3 ning
o„zi hisoblanadi, chunki 100 ta boshlang„ich berilganlar uchun x3-30x bilan x3 orasidagi farq
3%ni tashkil qiladi.
O„sish tezligi klassifikatsiyasi
Algoritmlarni ular murakkabligining o„sish tezligi bo„yicha sinflashtirish mukin. Bunda
klassifikatsiya uchta kategoriya bo„yicha amalga oshiriladi:a) murakkablik tezligi (tartibi yoki
o„sish funksiyasidagi tez o„suvchan qism funksiya) o„rtacha tezlik funksiyasi o„sish tezligi kabi
o„sib boruvchi algoritmlar; b) murakkablik tezligi o„rtacha tezlik funksiyasi bilan bir xil
tezlikda o„sib boruvchi algoritmlar; murakkablik tezligi o„rtacha tezlik funksiyasi o„sish
tezligidan sekin o„suvchi algoritmlar.
Katta omega Birinchi kategoriyaga taalluqli funksiyalar sinfi Ω(f) bilan belgilanadi. D funksiya
ushbu Ω sinfga taalluqli bo„ladi, qachonki n argumentning qandaydir oldindan belgilangan s
(musbat son) dan katta barcha qiymatlari uchun d(n)>cf(n) shart o„rinli bo„lsa.
Katta O
Uchinchi kategoriyaga taalluqli funksiyalar sinfi O(f) bilan belgilanadi. Ushbu sinf o„rtacha
qiymat tezligidan sekin o„sadigan funksiyalardan iborat. D funksiya ushbu sinfga taalluqli
bo„ladi, qachonki n argumentning qandaydir oldindan belgilangan s (musbat son) dan katta
barcha qiymatlari uchun d(n) Katta teta
Θ(f) bilan murakkablik tezligi o„rtacha tezlik funksiyasi bilan bir xil tezlikda o„sib boruvchi
funksiyalar sinfini belgilayiz. Formal nuqtai nazardan qaraganda ushbu sinf yuqorida keltirilgan
ikki sinfning kesishmasidan iboratdirdir: Θ(f)= Ω(f)∩ O(f).
Dasturlar tahlili
Faraz qilaylik, bizga katta va murakkab dastur berilgan bo„lsin. Ushbu dasturni tezroq ishlashini
qanday ta‟minlash mumkin? Dasturning qayta ishlanishi(modifikatsiyalanishi) mumkin bo„lgan
qismlarini qanday aniqlash mumkin? Buning uchun dasturdagi hisoblashlar va sikllar ko„p
bo„lgan qismdasturlarni aniqlab, ularni takomillashtirish mumkin bo„ladi. Ammo oldiniga dastur
ishida eng ko„p qatnashuvchi qismdasturlarni aniqlab olish kerak bo„ladi. Buning usullaridan biri
har bir qismdasturga global hisobchi qo„yishdan iborat. Ushbu hisobchi-o„zgaruvchilarning
boshlang„ich qiymati 0 ga tenglashtirilib, so„ngra qismdasturga har bitta murojaat vaqtida
qiymati bittaga oshirib boriladi. Dastur ishini tugatgach, hisobchilarning qiymatiga qarab, qaysi
qism dastur necha marta ishlagani ma‟lum bo„ladi.
O„rniga qo„yish bilan saralash algoritmi
Ushbu saralash algoritmining asosiy mohiyati saralangan ro„yxatga yangi element qo„shishda
uni “o„z joyiga” joylashtirishdan iboratdir. Bunda algoritm saralanuvchi ro„yxat birinchi
elementini uzunligi 1 ga teng bo„lgan saralangan ro„yxat deb qabul qilib, ikkinchi elementni
yangi yaratilayotgan saralangan ro„yxatning “kerakli” joyiga joylashtiradi. So„ngra berilgan
ro„yxatning uchinchi elementi ham saralangan ikki elementli ro„yxatdagi o„z joyiga
joylashtiriladi va hokazo. Ushbu jarayon berilgan ro„yxatning barcha elementlari saralangan
ro„yxatga joylashtirib chiqilgunga qadar davom ettiriladi. O„rniga qo„yish algoritmining ifodasi
quyidagidan iborat:
InsertSort(List,N)
List elementlarning saralanuvchi ro„yxati
N ro„yxatdagi elementlar soni
For i=2 to N do
newElement=list[i]
location=i-1
while (location) >=1) and(list[location]> newElement) do
{navbatdvgi elementdan kattalarini surish}
list[location+1]= list[location]
location= location-1
end while
list[location+1]= newElement
end For
Ushbu algoritm newElement o„zgaruvchisiga yangi o„rniga qo„yiluvchi qiymatni kiritadi.
So„ngra bu yangi elementga joy ajratish uchun massiv elementlari bir pozitsiyaga suriladi (while
sikli). Siklning oxirgi iteratsiyasi location+1 nomerli elementni location+2 pozitsiyaga
o„tkazadi,ya‟ni location+1 pozitsiyasi yangi element uchun bo„shatiladi.
Eng yomon holat tahlili
while siklida amallar eng ko„p bajariladi, qachonki ro„yxatning saralangan qismiga yangi
qo„shiluvchi element bu ro„yxat elementlarining barchasidan kichik bo„lsa. Bu holatda sikl
location o„zgaruvchisining qiymati 0 ga teng bo„lganda to„xtaydi.Shuning uchun har bir yangi
element ro„yxatning boshidan joy olsa, algoritm eng ko„p ish bajaradi. Bu faqat berilgan ro„yxat
elementlari kamayib borish tartibida joylashgan bo„lgandagina mumkindir.Bu holat eng yomon
holatlardan biridir.Bunday ro„yxatni qayta ishlash jarayoni quyidagicha aalga oshiriladi: birinchi
bo„lib berilgan ro„yxatning ikkinchi elementi joylashtiriladi.U faqat bitta element bilan
taqqoslanadi. Ikkinchi joylashtiriluvchi element oldingi ikkitasi bilan taqqoslanadi, uchinchisi
esa oldingi uchtasi bilan va hokazo i – element oldingi i ta element bilan taqqoslanadi. Shunday
qilib, jarayon N - 1 marta takrorlanadi. O„rniga qo„yishlar bilan saralash algoritmining
murakkabligi eng yomon holat uchun quyidagicha hisoblanadi:
( ) ∑
( )
( ) (
)
O„rtacha holat tahlili
Ushbu tahlil jarayonini ikki etapga ajratamiz. Oldiniga navbatdagi elementning pozitsiyasini
aniqlash uchun zarur bo„lgan taqqoslashlar o„rtacha sonini hisoblaymiz. So„ngra ushbu
miqdordan foydalanib barcha amallarning o„rtacha qiymatini hisoblash mumkin.Bitta element
uchun mumkin bo„lgan pozitsiyalar nechtagacha bo„ladi?
Saralangan ro„yxatga qo„shiluvchi birinchi element uchun ikkita umkin bo„lgan holat mavjud: u
ikki elementli ro„yxatda birinchi yoki ikkinchi pozitsiyani egallaydi. Ikkinchi elementda uchta
mumkin bo„lgan holat bo„ladi:birinchi, ikkinchi yoki uchinchi. Demak, i-element mumkin
bo„lgan i + 1 ta pozitsiyadan birini egallaydi. Faraz qilaylik, bu imkoniyatlarning ehtimoli o„zaro
teng bo„lsin. U holda i-elementni saralangan ro„yxatga qo„shish uchun bajariladigan barcha
amallarning o„rtacha qiymati quyigi formular bilan hisoblanadi:
(∑
) (
( )
)
Biz i-elementni saralangan ro„yxatga qo„shish uchun bajariladigan amallarning o„rtacha
qiymatini hisobladik. Endi ushbu natijani berilgan ro„yxatning N-1 ta elementlari uchun yig„ib
chiqamiz:
( ) ∑
∑ (
)
( ) (
)
Pufakchali saralash
Pufakchali saralash algoritmining mohiyati kichik qiymatlarning ro„yxat yuqorisiga itarilib, yirik
qiymatlarning ro„yxat pastiga surilishiga asoslangan. Pufakchali saralashning ko„p variantlari
mavjud bo„lib, ulardan birini ko„rib o„tamiz. Bunda algoritm ro„yxat bo„ylab bir necha o„tishni
bajaradi. Har bir o„tishda qo„shni elementlar bir-biri bilan taqqoslanadi.Agar bu elementlarni
tartibi noto„g„ri bo„lsa, ularning o„rinlari almashtiriladi.Har bir o„tish ro„yxat boshidan
boshlanadi. Oldin birinchi va ikkinchi element taqqoslanadi, keyin ikkinchi va uchinchisi va
hokazo. Bunda ro„yxatning eng katta elementi birinchi o„tish tugagandan keyin ro„yxatning
oxiridan joy oladi.Ikkinchi o„tishda kattalik bo„yicha ikkinchi element ixiridan ikkinchi o„rinni
egallaydi. Agar biror o„tishda bitta ham o„rin almashtirish bajarilmasa, bro„yxat saralangan deb
hisoblanib, algorit ishi to„xtatiladi. Quyida pufakchali saralash algoritmining ifodasi keltirilgan:
BubbleSort(list,N)
List Elementlarning saralanuvchi ro„yxati
N Ro„yxatdagi elementlar soni
Namber=N
swappedElamaents=true
while swappedElamaents do
Namber= Namber-1
swappedElamaents=false
For i=1 to Namber do
If list[i]> list[i+1] then
Swap(list[i], list[i+1])
swappedElamaents=true
end if
end for
end while
Eng yaxshi holat tahlili
Algoritm bajaradigan ishning xajmi minimal bo„lgan holatni ko„rib o„tamiz. Birinchi o„tishda
sikl to„liq bajarilganligi uchun algoritmda eng kamida N – 1 taqqoslash bajariladi.Bunda ikki
imkoniyat ko„rib chiqilishi kerak: birinchi o„tishda hech bo„lmasa bitta almashtirish bo„lgan;
almashtirish bo„lmagan. Birinchi holatda swappedElements o„zgaruvchisining qiymati rost,
demak N - 2 ta taqqoslashni talab qiluvchi while sikli takror bajariladi. Ikkinchi holatda
swappedElements o„zgaruvchisining qiymati yolg„on, demak algoritm bajarilishi
to„xtaydi.Shuning uchun eng yaxshi holatda N – 1 ta taqqoslashlar bajarilib, birinchi o„tishda
o„rin almashtirishlar bo„lmaydi. Bundan eng yaxshi berilganlar to„plami talab qilingan tartibda
joylashgan elementlar ro„yxatidan iborat ekanligi bildiradi.
Eng yomon holat tahlili
Eng yaxshi holatda berilganlar to„plami talab qilingan tartibda joylashgan elementlardan iborat
bo„lsa, eng yomon holatda berilganlar teskari tarbida joylashgan elementlardan iborat bo„lishi
mumkinmi? Agar eng katta element ro„yxatda birinchi turgan bo„lsa, u barcha qolgan elementlar
bilan o„rin almashtirib chiqishi kerak. Birinchi o„tish boshida kattalik bo„yicha ikkinchi element
ikkinchi o„rinni egallab turadi, ammo birinchi taqqoslash va o„rin almashtirishdan natijasida u
birinchi o„ringa o„tkaziladi. Ikkinchi o„tish boshida ro„yxat boshida kattaliu bo„yicha ikkinchi
elemment turadi va u qolgan barcha elementlar bilan o„rin almashadi.Bu jarayon barcha qolgan
elementlar uchun takrorlanganligi uchun For sikli N - 1 marta bajariladi. Shunday qilib, eng
yomon holatda nechta taqqoslash bajariladi? Birinchi o„tishda qo„shni qiymatlarni N – 1
taqqoslash bajariladi, ikkinchi o„tishda N - 2 ta. Har bir keyingi o„tishda taqqoslashlar soni 1 ga
kamayadi. Shuning uchun eng yomon holat uchun murakkablik quyidagi forula bilan
hisoblanadi:
( ) ∑ ∑
( )
(
)
Do'stlaringiz bilan baham: |