Algoritmlash

Nima uchun bosh harflar

bo Hozircha kani sondagi ijrochilar bilan tanishdik. Keyingi blarda ularning soni ko'payadi. Albatta, qo‘llanmada uchra-

maydigan juda ko‘p sondagi Ijrochilarni o'ylab topish mumkin. Har bir Ijrochi uchun o'zining ko‘rsatmalar (yoki qoidalar)

tizimi bor. Lekin quyidagi takrorlash tuzilmasi TAKRORLANSIN MARTA

lozim bo‘lgan koTsatmalar>

barc TAMOM bir xil. U qaysi Ijrochi bilan ish ko‘rayot- ganihasi uchuniq emas va hammasiga mos kelaveradi. Tuzilma uni mizga bogM r qanday Ijrochi uchun algoritm tuzishga imkon b versaldir —ha a algoritmlashda asosiylaridan biridir.

eradi. Bu tuzilm

— Yuzlab va minglab Ijrochilar bor. Lekin lTAKRORLANSIN

MARTA ko‘rinishidagi universal tuzilma ar juda kam va bu algoritmlashning asos xossasidir. Asosiy tuzilmalar bor-yo‘g‘i uchta. Ba’zan qulaylik uchun bir nechta qo‘shimcha tuzilmalar qoMlab ham turiladi. Agar siz qoMlanmaning asosiy maqsadi — bu tuzilmalardan foydalanish san'atini oTgatish deb hisob- lasangiz, deyarli xato qilmaysiz. Algoritmik tafakkur va algoritm- lashning kaliti - bu universal tuzilmalami erkin qoMlay bilishdir.

Doimo, universal tuzilmalarni tashqi ko'rinishidan Ijrochilar

ko‘rsatmasidan farqlash uchun bosh harflar bilan yozamiz.

Samaradorlik va murakkablik

o‘ Biz turli algoritmlarning samaradorligini muhokama qilib bitdik. AJgoritmning bajarilish qadami —bu Ijrochi tomonidan altta koTsatmaning bajarilishidir. Bir masalaniihal etuvchi ikkita goritmdan kam qadam talab qilinayotgan samaraliroqdir.

Samaradorlik oMchovi - bu bor-yo‘g‘i qadamlar sonidir.

66

to Lekin chuqurroq e'tibor berib qarasak, bu ta’rifdagi mujmal lamonlarni kaniqlaymiz. Ba’zan aavval uchragan oalgoritm- rdagidan o‘ra vaziyat murakk broq bo‘ladi. H zircha bu

masalaga chuqurlashib o‘tirmaymiz va chuqurroq bilim to'pla-

maguncha uning muhokamasini keyinga qoldiramiz. Algoritmlar murakkabligi bilan ham farqlanishi mumkin. Algoritmning murakkabligini uning matnidagi satrlar soni bilan o‘lchaymiz.

Shu bilan birga quyidagi ikki satrni bir tuzilmaning ikki qismi bo‘lgani uchun bittaga hisoblaymiz:

TAKRORLANSIN MARTA TAMOM

1 ni qMana, masalan, quyidagi algoritmda:

TAK o‘shLANSIN 6 MARTA

ROR

2 ga ko‘paytir

1 ni qo‘sh TAMOM

1 ni qfaqat 4 ta satr:

TAK o‘shLANSIN 6 MARTA

ROR

TAMOM

2 ga ko‘paytir

1 ni qo‘sh

bor. Bu uning murakkabligi 4 ekanligini bildiradi.

Shuni aytib o‘tish joizki, II bobdagi barcha algoritmlarning barchasini murakkabligi va samaradorligi o‘zaro tengdir. Ma- salan, bo‘ri, echki va karamni daryodan o'tkazish algoritmi ham 7 satrdan iborat ham u 7 qadamda bajariladi. Bu kabilar shu bobning barcha algoritmlari uchun ham o'rinli. Bizda shu vaqt- gacha algoritm matnidagi satrlarini qisqartirish uchun vosita yo‘q edi. Bizdan algoritm ko‘rsatmasini bajarish talab etilgan bo‘lsa, biz ko'rsatmani algoritm matniga joylashtirishga majbur edik.

alg Masalan, Oshiruvchi atomonidan 17gsonini hosil iqilish

oritmiga qarang: 17 m rta bajarilish al oritm matnin ng 17

satriga aylandi.

- Endi esa bizni kerakli vositamiz bor: bu TAKRORLANSIN

s MARTA tuzilmasi. Shuning uchun Oshiruvchi tomonidan 17

onini hosil qilish algoritmi 3 satrdan iborat bo‘ladi (eslatamiz:

tuzilma 1 ta satr deb hisoblanadi):

67



1 ni qo‘sh

TAKRORLANSIN 16 MARTA

1 ni qo‘sh

E TAMOMoritmning samaradorligi 17 ga, murakkabligi esa

ndi bu alg

17 emas, 3 ga teng. Askarlar va qayiq masalasi algoritmida 60 ta askarni daryodan o'tkazish uchun 240 qadam bajariladi, algoritm matni esa 5 satrdan iborat. Bu algoritmning samara- dorligi 240 ga, murakkabligi esa 5 ga teng.

sonBaqa uchun tuzilgan 4.6 - masalani algoritmida qadamlar

ini hisoblaymiz:

son + 1 + son — 1 = (n —1):2 + (n — 1):2 — n — \.

Demak, har qanday n toq son uchun algoritm ning samaradorligi n —I ga teng ekan. Algoritmning murakkabiigi esa n toq son nechaga teng boMishidan qat'iy nazar, 5 ga teng bo‘ladi.