Ota-onamga iit bombayga Do'stlarimga -laxmi va Modaya Barcha mehnatkashlarga Mening oilam a'zolarimga

MA'LUMOT TUZILMALARI VA ALGORITMLAR Oson
Machine Translated by Google

---

Machine Translated by Google

---

2-bob ALGORITMLARNING TAHLILI
Nima uchun algoritmlarni tahlil qilish kerak?
Kirish
Algoritm nima?
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
57
Algoritmlar tahlili | Kirish
©www.CareerMonk.com
Yaxshiroq tushunish uchun keling, omlet tayyorlash muammosini ko'rib chiqaylik. Tuxumdonni tayyorlash uchun biz quyidagi umumiy bosqichlarni bajaramiz:
Algoritm - bu berilgan masala bo'yicha bosqichma-bosqich ko'rsatmalar.
i. Ha bo'lsa, uni panga soling.
shaharga
2) Yog 'oling. a. Bizda
neft bormi?
1. Ha bo'lsa, tashqariga chiqing va sotib oling.
Xuddi shunday, kompyuter fanida bir xil muammoni hal qilish uchun bir nechta algoritmlar mavjud bo'lishi mumkin (uchun
ii. Agar yo'q bo'lsa, biz neft sotib olishni xohlaymizmi?
Agar biz shahardan ketmoqchi bo'lsak, buni qilishning ko'p usullari bo'lishi mumkin: reysda, avtobusda, poezdda va velosipedda. Mavjudligi va qulayligiga
qarab, biz o'zimizga mos keladiganini tanlaymiz.
3) Pechni yoqing va hokazo.
Biz nima qilyapmiz, ma'lum bir muammo uchun (omlet tayyorlash), uni hal qilishning bosqichma-bosqich tartibini ko'rsatamiz. Algoritmning rasmiy ta'rifi
quyidagicha berilishi mumkin:
2. Agar yo'q bo'lsa, biz tugatishimiz mumkin.
Ushbu bobning maqsadi algoritmlarni, ularning belgilarini, munosabatlarini tahlil qilish va iloji boricha ko'proq muammolarni hal qilishning ahamiyatini
tushuntirishdir. Biz birinchi navbatda tahlilning ahamiyatini tushunishga e'tibor qaratamiz, so'ngra sekin-asta turli xil belgilar bilan algoritmlarni va nihoyat,
muammolarni tahlil qilishga o'tamiz. Ushbu bobni tugatgandan so'ng, siz har qanday algoritmning murakkabligini (ayniqsa, rekursiv funksiyalarni) topa
olishingiz kerak.
1) Qovurilgan idishni oling.
Algoritmlarni yozishda yodda tutish kerak bo'lgan muhim eslatma: biz algoritmning har bir bosqichini isbotlashimiz shart emas.
Machine Translated by Google

---

Faraz qilaylik, biz berilgan algoritmning ishlash vaqtini kirish hajmiga qarab ifodaladik
Kirish funksiyasi sifatida ish vaqtining ortishi tezligi siz mashina va velosiped sotib olish
uchun do'konga borganingiz deb ataladi. Agar do'stingiz sizni u erda ko'rib, nima sotib olayotganingizni so'rasa, biz umuman
aytamiz, chunki bu mashinaning narxi tsikl narxiga nisbatan juda katta (
• Polinom darajasi •
Matritsadagi elementlar soni
Amalga oshirilgan bayonotlar soni?
. Faraz qilaylik
Umumiy xarajat = avtomobil_narxi + sikl_narxi
• Kirishning ikkilik tasviridagi bitlar soni
Masalan, saralash muammosi qo'shish tartibi, tanlovni saralash, tez tartiblash va boshqalar kabi ko'plab algoritmlarga ega.
dasturlash tili, shuningdek, individual dasturchining uslubi.
ortadi. Kirish hajmi - kirishdagi elementlar soni va muammo turiga qarab kirish har xil bo'lishi mumkin. Umuman olganda, biz
quyidagi turdagi kirishlarga duch kelamiz.
.
Taqqoslash mashina vaqtiga, dasturlash uslubiga va hokazolarga bog'liq emas.
sikl narxini avtomobil narxiga yaqinlashtirish).
Amalga oshirish vaqtlari?
• Massivning o‘lchami
chunki bajarish vaqtlari ma'lum bir kompyuterga xosdir.
)
(ya'ni, biz ishlash vaqtlari va shunga o'xshash turli xil funktsiyalarni solishtirishimiz mumkin
chunki bayonotlar soni har xil bo'ladi
Bu muammoning o'lchami (kirish hajmi) sifatida ishlov berish vaqti qanday oshishini aniqlash jarayonidir.
.
Avtomobilning umumiy qiymati (taxminan)
Ideal yechim?
Algoritm tahlili ularning qaysi biri sarflangan vaqt va makon jihatidan samarali ekanligini aniqlashga yordam beradi.
Maqsad algoritmlarni (yoki yechimlarni) asosan ish vaqti nuqtai nazaridan, balki boshqa omillar (masalan, xotira, ishlab
chiquvchining harakatlari va boshqalar) jihatidan solishtirishdir.
Algoritmlarni solishtirish uchun ba'zilarini aniqlaylik
• Grafikdagi uchlari va qirralari
Ishlash vaqti tahlili nima?
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
58
Algoritmlar tahlili | Algoritmlar tahlilining maqsadi?
©www.CareerMonk.com
O'sish sur'ati nima?
Algoritmlarni qanday solishtirish mumkin?
Algoritmlar tahlilining maqsadi?
Machine Translated by Google

---

Yuqoridagi misol uchun biz avtomobil narxini va tsikl narxini funktsiya jihatidan ifodalashimiz mumkin va berilgan
funktsiya uchun nisbatan ahamiyatsiz bo'lgan past tartibli shartlarni e'tiborsiz qoldiramiz (kirish hajmining katta
qiymati uchun, ). Quyidagi holatda misol sifatida, , va ba'zi funktsiyalarning individual xarajatlari va
ga yaqinlashamiz. Chunki,
eng yuqori o'sish sur'ati hisoblanadi.
,
Quyidagi diagrammada turli xil o'sish sur'atlari o'rtasidagi bog'liqlik ko'rsatilgan.
a
s
c
a
w
r
t
r
D
g
t
R
e
o
i
f
O
n
G
e
e
s
h
ÿ
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
59
Algoritmlar tahlili | Odatda ishlatiladigan o'sish tezligi
Odatda ishlatiladigan o'sish tezligi
Machine Translated by Google

---

kub
Tartiblangan massivda elementni topish
• Eng yaxshi holat
,
o Algoritm katta vaqt talab qiladigan kirishni belgilaydi.
Misol
Matritsalarni ko'paytirish
eng yomon holatda
Berilgan algoritm uchun biz eng yaxshi holat, eng yomon holat va o‘rtacha holat tahlilini ifodalar ko‘rinishida ifodalashimiz
mumkin. Misol tariqasida, keling
Algoritmni tahlil qilish uchun bizga qandaydir sintaksis kerak bo'ladi va u asimptotik tahlil/notatsiya uchun asos bo'ladi.
Tahlilning uch turi mavjud:
Vaqt murakkabligi nomi
Kvadrat
• Average case o
Algoritmning ishlash vaqti haqida bashorat beradi
Saralanmagan massivda elementni topish
Agar bizda muammoning algoritmi mavjud bo'lsa va algoritm qaysi kirishlar uchun kamroq vaqt talab qilishini (yaxshi
ishlashini) va qaysi kirishlar uchun algoritm juda ko'p vaqt talab qilishini bilmoqchi bo'lsak.
o Algoritm eng kam vaqt talab qiladigan kirishni belgilaydi.
Logarifmik
Eksponensial
eng yaxshi holat uchun
Xanoy minoralari muammosi
Bog'langan ro'yxatning old qismiga element qo'shish
o Kirish algoritmi sekinroq ishlaydi.
berilgan algoritmni ifodalovchi funksiya bo‘lsin.
Grafikdagi ikkita tugun orasidagi eng qisqa yo'l
• Eng yomon holat
Doimiy
Chiziqli logarifmik saralash n ta elementni “bo‘l va zabt et”-Birlashtirish
Quyida qolgan boblarda uchraydigan o'sish sur'atlari ro'yxati keltirilgan.
Algoritmni ifoda ko‘rinishida ifodalash mumkinligini allaqachon ko‘rib chiqdik. Bu shuni anglatadiki, biz algoritmni bir nechta
ifodalar bilan ifodalaymiz: biri kamroq vaqt talab qiladigan holat uchun, ikkinchisi esa ko'proq vaqt talab qiladigan holatlar
uchun. Umuman olganda, birinchi holat eng yaxshi holat, ikkinchi holat esa algoritm uchun eng yomon holat deb ataladi.
o Kirish tasodifiy ekanligini taxmin qiladi
o Kirish - bu algoritm eng tez ishlaydigani.
Chiziqli
60
Algoritmlar tahlili | Tahlil turlari
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
Tahlil turlari
Machine Translated by Google

---

. Bu degani
kabi kichikroq yoki bir xil o'sish tartibiga ega bo'lgan funktsiyalar to'plami
hisoblanadi
,
Xuddi shunday, o'rtacha holat uchun ham. Ifoda algoritm o'rtacha ishlash vaqtini (yoki xotirani) oladigan kirishlarni belgilaydi.
Eslatma: Algoritmlarni faqat kattaroq qiymatlarda tahlil qiling. Buning ma'nosi shundaki, quyida biz o'sish tezligiga ahamiyat
bermaymiz.
.
Misol uchun,
agar uchun o'sishning maksimal tezligini beradi
.
berilgan algoritm bo'lsa, u holda
kattaroq qiymatlarda bo'ladi.
Keling, belgini biroz batafsilroq ko'rib chiqaylik. musbat
konstantalar va shunga bog'liq bo'lganlar.
Bizning maqsadimiz eng kichik o'sish algoritmlarini o'sish tezligini
berishdir. Umuman olganda,
biz ning past qiymatlarini rad etamiz. Bu shuni anglatadiki, past qiymatlarda o'sish tezligi muhim emas. Quyidagi rasmda biz
ma'lum bir algoritm uchun o'sish tezligini hisobga olishimiz kerak bo'lgan nuqtadir. Pastda o'sish tezligi boshqacha bo'lishi
mumkin.
o'z ichiga oladi
Masalan,
berilgandan
katta yoki teng bo'lgan asimptotik
qattiq yuqori mavjud
Bu belgi berilgan funksiyaning yuqori chegarasini beradi. Odatda biz uni sifatida ifodalaymiz. Bu degani, yuqori
chegaraning katta qiymatlarida
va boshqalar..
Eng yaxshi holat, o'rtacha holat va eng yomon holat uchun iboralarga ega bo'lgan holda, uchta holat uchun biz yuqori
chegarani, pastki chegarani aniqlashimiz kerak. Ushbu yuqori va pastki chegaralarni ifodalash uchun bizga qandaydir
sintaksis kerak va bu keyingi muhokama mavzusi. Faraz qilaylik, berilgan algoritm funksiya ko'rinishida ifodalangan
Big-O vizualizatsiyasi
.
.
notation barcha uchun sifatida
belgilangan
Kirish hajmi,
O'sish sur'ati
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
61
Algoritmlar tahlili | Asimptotik belgi?
Asimptotik belgi?
Big-O belgisi
Machine Translated by Google

---

,
.
,
.
va
Misol-1 uchun yuqori chegarani toping
=
Barcha uchun
va
Barcha uchun
va
Misol-5 uchun yuqori chegarani toping
Yechim:
Barcha uchun
=
ÿ
Yechim:
bilan
hamma uchun
bilan c = 4 va
Misol-3 uchun yuqori chegarani toping
ÿ =
4-misol uchun yuqori chegarani toping
Yechim:
ÿ
bilan
Yechim:
bilan
hamma uchun
ÿ
bilan
=
Misol-2 uchun yuqori chegarani toping
bilan
ÿ
Misol-6 uchun yuqori chegarani toping
ÿ
Yechim:
va
va
=
Barcha uchun
Yechim:
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
62
Algoritmlar tahlili | Big-O belgisi
Big-O misollar
Machine Translated by Google

---

ÿ misollar
O'ziga xoslik yo'qmi?
Omega-ÿ belgisi
63
Algoritmlar tahlili | Omega-ÿ belgisi
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
ning qattiqroq pastki chegarasi
va
ijobiy konstantalar mavjud va shunga o'xshash
Shunday
qilib: bilan
Barcha uchun
Misol-1 uchun pastki chegarani toping
Yechim 1:
,
Asimptotik chegaralar uchun va ularni isbotlashda yagona qiymatlar to'plami mavjud emas. Keling, ko'rib chiqaylik,
va
Yechim:
.
yechim.
Masalan, agar
ÿ
uchun asimptotik qattiq pastki chegara hisoblanadi
yechim hisoblanadi.
hisoblanadi
va = 1
Yechim:
Barcha uchun
Munozaraga o'xshab, bu belgi berilgan algoritmning pastki chegarasini beradi va biz uni quyidagicha ifodalaymiz. Bu shuni
anglatadiki, kattaroq qiymatlarda
eng katta o'sish sur'atini beradi
Shu kabi:
ham a
Belgilanishni quyidagicha aniqlash mumkin
Bu funksiya uchun bir nechta va qiymatlar mavjud.
2-misol isbotlang
Barcha uchun
hisoblanadi
va = 1
,
Yechim 2:
Bizning maqsadimiz
berilgan algoritmlarning o'sish tezligidan kamroq yoki unga teng bo'lishidir
Kirish hajmi,
O'sish sur'ati
Machine Translated by Google

---

Yechim:
va = 1
hisoblanadi
.
.
-
uchun
Bu belgi berilgan funksiya (algoritm) ning yuqori va pastki chegaralari bir xil yoki bir xil emasligini hal qiladi.
asimptotik qattiq bog'langan
,
ÿ
va shunga o'xshash
Algoritmning o'rtacha ishlash vaqti har doim pastki chegara va yuqori chegara o'rtasida bo'ladi. Agar yuqori chegara ( ) va pastki
chegara ( ) bir xil natijani bersa, yozuv ham bir xil o'sish tezligiga ega bo'ladi. Misol tariqasida, bu ifoda deb faraz qilaylik. Keyin, uning
qattiq yuqori chegarasi. Eng yaxshi holatda o'sish sur'ati - Bu holda, eng yaxshi va eng yomon holatda o'sish tezligi bir xil bo'ladi.
Natijada, o'rtacha holat ham bir xil bo'ladi. Berilgan funktsiya (algoritm) uchun va uchun o'sish tezligi (chegaralari) bir
xil bo'lmasa, o'sish holining tezligi bir xil bo'lmasligi mumkin.
bilan
Misol-3
Barcha uchun
Yechim:
Misol-1 uchun bog'langan thni toping
ijobiy konstantalar mavjud
Barcha uchun,
faqat amal qiladi:
ÿ
Qarama-qarshilik: doimiydan kichik bo'lishi mumkin emas
kabi o'sish tartibiga ega bo'lgan funktsiyalar to'plami
Chunki ijobiy
-
Endi belgi ta'rifini ko'rib chiqing. Bu sifatida belgilanadi
2-misol isbotlang
O'sish sur'ati
Kirish hajmi,
64
Algoritmlar tahlili | Theta-th notation
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
Theta-th notation
ÿ Misollar
Machine Translated by Google

---

Nega u asimptotik tahlil deb ataladi?
Asimptotik tahlil uchun ko'rsatmalar?
Muhim eslatmalar
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
65
Algoritmlar tahlili | Nega u asimptotik tahlil deb ataladi?
©www.CareerMonk.com
Matematikada bunday egri chiziqni asimptotik
egri chiziq deb ataymiz
uchun (i=1; i<=n; i++)
Yechim:
3-misol isbotlang
shuningdek, taxminan bo'lgan egri chiziqdir
1) Looplar: siklning ishlash vaqti, eng ko'p, tsikl ichidagi bayonotlarning ishlash vaqtidir.
(algoritm) yuqori chegarani ( ) va pastki chegarani ( ) va o'rtacha ishlash vaqtini ( ) olish har doim ham mumkin bo'lmasligi mumkin.
Misol uchun, agar biz algoritmning eng yaxshi holatini muhokama qilsak, biz yuqori chegara ( ) va pastki chegara ( ) va o'rtacha
ishlash vaqtini ( ) berishga harakat qilamiz.
da
// vaqtlarni bajaradi
Yechim:
{
faqat amal qiladi:
bir xil.
.
Yuqoridagi muhokamadan (har uchta belgi uchun: eng yomon holat, eng yaxshi holat va o'rtacha holat), biz har bir holatda ning
yuqori qiymatlariga yaqin bo'lgan berilgan funktsiya uchun buni osongina tushunishimiz mumkin. Bu shuni anglatadiki, ning yuqori
qiymatlari.
4-misol isbotlang
.
}
Algoritmning ishlash vaqtini aniqlashda bizga yordam beradigan ba'zi umumiy qoidalar mavjud. Quyida ulardan bir nechtasi keltirilgan.
- Mumkin emas
biz boshqa funktsiyani topishga harakat qilamiz
Qolgan boblarda biz odatda yuqori chegaraga ( ) e'tibor qaratamiz, chunki algoritmning pastki chegarasini ( ) bilish amaliy ahamiyatga
ega emas va agar yuqori chegara ( ) va pastki chegarasi ( ) bo'lsa, biz yozuvdan foydalanamiz.
ÿ 6 ÿ
ÿ
Tahlil qilish uchun (eng yaxshi holat, eng yomon holat va o'rtacha) biz yuqori chegara ( ) va pastki chegara ( ) va o'rtacha ish vaqtini
berishga harakat qilamiz. Yuqoridagi misollardan ma'lum bir funktsiya uchun ham aniq bo'lishi kerak
Boshqacha aytganda,
(shu jumladan testlar) iteratsiyalar soniga ko'paytiriladi.
ÿ
Shuning uchun biz algoritm tahlilini deb ataymiz
m = m + 2; // doimiy vaqt, c
bo'ladi
Machine Translated by Google

---

//tashqi sikl n marta bajarildi
the
// sinov: doimiy
}
Umumiy vaqt = doimiy
Umumiy vaqt
//ichki sikl n marta bajarildi
qismi
x = x +1; // doimiy vaqt
k = k+1; // doimiy vaqt
yoki
//tashqi sikl n marta bajarildi
agar (uzunlik ( ) != otherStack. uzunlik ( ) ) {
// ichki tsikl n marta bajarildi
uchun (i=1; i<=n; i++) {
}
k = k+1; // doimiy vaqt
}
4) If-then-else iboralari: Eng yomon ish vaqti: test, ortiqcha (qaysi biri kattaroq bo'lsa).
the
}
uchun (i=1; i<=n; i++) {
// n marta bajarildi
uchun (i=1; i<=n; i++) {
2) Ichki halqalar: ichkaridan tashqariga tahlil qiling. Umumiy ish vaqti barcha pastadirlarning o'lchamlari mahsulotidir.
3) Ketma-ket gaplar: Har bir gapning vaqt murakkabliklarini qo'shing.
uchun (j=1; j<=n; j++) {
uchun (j=1; j<=n; j++) {
m = m + 2; // doimiy vaqt
Umumiy vaqt
qismi
yolg'onni qaytarish; //keyin qism: doimiy
}
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
66
Algoritmlar tahlili | Asimptotik tahlil uchun ko'rsatmalar?
Machine Translated by Google

---

i = i*2;
//agar baza-2 deb faraz qilsak
i = i/2;
yolg'onni qaytarish;
}
}
Agar diqqat bilan kuzatadigan bo'lsak, i qiymati har safar ikki barobar ortadi. Dastlab keyingi
qadamlar va boshqalar.
Eslatma: Shunga o'xshab, quyida keltirilgan holatlar uchun ham o'sishning eng yomon sur'ati
ketma-ketlikni pasaytirish uchun ham yaxshi bo'ladi.
Umumiy vaqt
keyingi bosqichda
Ya'ni, xuddi shunday
{
}
// boshqa agar : doimiy + doimiy (boshqa qism yo'q)
agar muammo hajmini a ga qisqartirish uchun doimiy vaqt kerak bo'lsa
va biz chiqamiz
// doimiy
uchun (i=1; i<=n;)
{
( )
Shunday qilib, umumiy vaqt
n
}
5) Logarifmik murakkablik: Algoritm kasrdir (odatda ).
// else qismi: (doimiy + doimiy) * uchun (int n
= 0; n < uzunlik( ); n++) {
boshqa
}
Faraz qilaylik, tsikl bir necha marta bajarilmoqda. Bu loopda degan ma'noni anglatadi.
Shunday qilib, agar ikkala tomonda ham logarifm olsak,
agar (!list[n].equals(otherStack.list[n]))
Misol tariqasida quyidagi dasturni ko'rib chiqamiz:
qadam
uchun (i=n; i<=1;)
{
va ichida
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
67
Algoritmlar tahlili | Asimptotik tahlil uchun ko'rsatmalar?
Machine Translated by Google

---

Arifmetik qator
va uchun ham amal qiladi.
ÿ
va
Geometrik qator
Yana bir misol algoritmi ikkilik qidiruv: sahifalar lug'atida so'zni topish
agar va faqat agar
va faqat agar bo'lsa
ÿ
va uchun ham amal qiladi.
Harmonik seriyalar
Logarifmlar
ÿ ÿ
-
• Lug‘atning markaziy nuqtasiga qarang
• So‘z topilguncha jarayonni lug‘atning chap yoki o‘ng qismi bilan takrorlang
Boshqa muhim formulalar
• So‘z markazdan chapgami yoki o‘nggami?
• Tranzitivlik: •
Reflektorlik: •
Simmetriya: •
Transpozitsiyali simmetriya:
ÿ
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
68
Algoritmlar tahlili | Belgilarning xossalari
Bo'lish va zabt etish uchun asosiy teorema
Ko'p ishlatiladigan logarifmlar va yig'indilar
Belgilarning xossalari
Machine Translated by Google

---

Masalalar “Bo‘lish va yengish” asosiy teorema
1)
2)
3)
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
69
Algoritmlar tahlili | Masalalar “Bo‘lish va yengish” asosiy teorema
b. Agar
,
keyin
(
(Master teorema hol 3.a)
Muammo-3
Yechim:
=> Qo'llanilmaydi (doimiy emas)
agar takrorlanish mumkin bo'lsa
(Master teorema ishi 3.a)
Barcha bo'lish va zabt etish algoritmlarida biz muammoni har biri asl muammoning bir qismi bo'lgan kichik
muammolarga ajratamiz, so'ngra yakuniy javobni hisoblash uchun qo'shimcha ishlarni bajaramiz. Misol tariqasida,
agar biz birlashtirish tartibini ko'rib chiqsak [batafsil ma'lumot uchun, bobga qarang], u har biri asl hajmining yarmiga
teng bo'lgan ikkita kichik muammo ustida ishlaydi va keyin birlashtirish uchun qo'shimcha ishlarni ishlatadi. Bu ish
vaqti tenglamasini beradi:
keyin
keyin
( ( )
,
,
b. Agar
Quyidagi teoremadan bo'lish va zabt etish algoritmlarining ishlash vaqtini aniqlash mumkin. Berilgan dastur (algoritm)
uchun birinchi navbatda muammoning takrorlanish munosabatini topishga harakat qilamiz. Agar takrorlanish quyidagi
shaklda bo'lsa, biz to'liq hal qilmasdan to'g'ridan-to'g'ri javob beramiz.
Yechim:
Yechim:
,
Muammo-2
Muammo-5
raqam, keyin:
)
)
va haqiqiydir
a. Agar
keyin
,
(Master teorema ishi 2.a)
Quyidagi takrorlanishlarning har biri uchun asosiy teorema bilan hal qilingan ish
vaqti uchun ifoda bering. Aks holda, asosiy teorema qo'llanilmasligini ko'rsating.
Yechim:
)
c. Agar
Agar takrorlanish shaklda bo'lsa
(((
Muammo-4
( )
keyin
a. Agar
qayerda
)
)
keyin
Muammo-1
,
Machine Translated by Google

---

Yechim:
Yechim:
ÿ
(Master teorema ishi 2.b)
ÿ (Master teorema 1-holati)
(Master teorema 1-holati)
Muammo-17
ÿ
Yechim:
Muammo-18
(Master teorema 1-holati)
Yechim:
Muammo-11
Muammo-14
(Master teorema 1-holati)
Muammo-9
Qo'llanilmaydi (funktsiya ijobiy emas)
(Master teorema ishi 3.a)
Muammo-6
ÿ
Muammo-15
Yechim:
(Master teorema ishi 2.a)
Qo'llanilmaydi (
Yechim:
Yechim:
Muammo-10
Muammo-13
ÿ
(Master teorema 1-holati)
(Master teorema 1-holati)
Muammo-16
Yechim:
Muammo-8
(Master teorema ishi 3.a)
Yechim:
Yechim:
Yechim:
(Master teorema ishi 3.b)
Yechim:
Muammo-7
)
(Master teorema 3.as)
Yechim:
Yechim:
Muammo-12
70
Algoritmlar tahlili | Masalalar “Bo‘lish va yengish” asosiy teorema
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
Machine Translated by Google

---

Ayirish va zabt etish bosh teoremasining varianti
Ayirish va yengish takrorlanishlari uchun asosiy teorema
Algoritmlarni tahlil qilish masalalari
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
71
Algoritmlar tahlili | Ayirish va yengish takrorlanishlari uchun asosiy teorema
©www.CareerMonk.com
( ) ( )
( ) {
(
(
pozitivda aniqlangan va xususiyatga ega bo'lgan funksiya bo'lishi kerak
Muammo-19
{
Tenglama konstantalarining yechimi,
bo'ladi
Muammo-21
Quyidagi takrorlanishning murakkabligini toping:
va funksiya
va
Yechish: Keling, bu funktsiyani almashtirish bilan hal qilishga harakat qilaylik.
(Master teorema ishi 3.a)
)
Yechim:
ichida joylashgan
,
,
Eslatma: Quyidagi muammolardan biz qanday hollarda turli xil murakkabliklarni olishimizni tushunishga harakat qiling
va boshqalar..).
Mayli
Agar
Muammo-20
Yechim:
ba'zi doimiylar uchun
qayerda
{
(Master teorema 2.a ishi)
keyin
bor
Machine Translated by Google

---

Muammo-22
Quyidagi takrorlanishning murakkabligini toping:
ÿ Murakkablik E'tibor bering, takrorlanish munosabati eksponensial ko'rinsa-da, bu erda takrorlanish munosabatining yechimi boshqacha
natija beradi.
int s=1 ;
s= s+i ;
{
// s 1 emas, balki i tezlikda ortib bormoqda
Yechish: Keling, bu funktsiyani almashtirish bilan echishga harakat qilaylik.
i++;
Bu ushbu funktsiyaning murakkabligini aniq ko'rsatadi
qiymat)
}
int s=1 ;
i++;
Muammo-23
Quyidagi funktsiyaning ishlash vaqti qancha (kirish funktsiyasi sifatida ko'rsatilgan
chop etish (\*");
while( s <= n) {
{
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
int i=1 ;
Ushbu muammo uchun asosiy teorema.
void funktsiyasi (int n)
Eslatma: Biz foydalanishimiz mumkin
.
}
{
while( s <= n) {
void funktsiyasi (int n)
int i=1 ;
72
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
Machine Translated by Google

---

count++;
Har bir iteratsiya uchun bittaga ortish qiymati
birinchi musbat sonlarning yig'indisidir. Agar bo'lsa
ÿ . Mantiqiy fikr bir xil
,
,
hisoblash =0;
count++;
int i, hisoblash =0;;
}
uchun(j=1; j + n/2<=n; j= j++)
int i, hisoblash =0;;
chop etish ("*");
void funktsiyasi (int n)
hisoblash =0;
{
bekor funktsiyasi (int n)
ÿ
void funktsiyasi (int n)
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing.
Yuqoridagi funktsiyada tsikl tugaydi, agar muammo-23.
=
}
count++;
for(k=1; k<=n; k= k * 2)
Munosabatlar iteratsiyasiga qarab atamalarni belgilashimiz
mumkin. Shunday qilib, da mavjud qiymat
for(i=1; i*i<=n; i++)
}
int i, j, k
for(i=n/2; i<=n; i++)
{
for(i=1; i*i<=n; i++)
}
int i, j, k
bekor funktsiyasi (int n)
Masala-24
Quyida berilgan funksiyaning murakkabligini toping.
s= s+i ;
{
{
}
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
dastur tomonidan qabul qilingan iteratsiyalarning umumiy soni, keyin esa while tsikli bir marta tugaydi.
Muammo-25
Quyidagi dasturning murakkabligi nimadan iborat:
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
73
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
Machine Translated by Google

---

Yuqoridagi funktsiyaning murakkabligi
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing.
int i, j, k
for(i=n/2; i<=n; i++)
int i, j, k //
tashqi sikl n/2 marta for(i=n/2; i<=n;
i++) bajariladi
Masala-27
Quyidagi dasturning murakkabligini toping. funktsiya ( int
n ) {
chop etish ("*");
bekor funktsiyasi (int n)
{
hisoblash =0;
//tashqi sikl n/2 marta bajariladi (i=n/
2; i<=n; i++)
hisoblash =0;
,
for( j= 1 ; j <= n ; j + + ) {
for(j=1; j<=n; j= 2 * j)
for(k=1; k<=n; k= k * 2)
//O'rta sikl logn vaqtlarini for(j=1; j<=n;
j= 2 * j) bajaradi //tashqi
sikl logn vaqtlarini for(k=1; k<=n; k=
k*2) bajaradi.
count++;
}
}
//O'rta sikl n/2 marta for(j=1; j + n/2<=n;
j= j++) //tashqi sikl logn
vaqtlarini for(k=1; k<=n; k= k) bajaradi
* 2)
}
,
count++;
count++;
Muammo-26
Quyidagi dasturning murakkabligi nimadan iborat:
bekor funktsiyasi (int n)
{
Yuqoridagi funktsiyaning murakkabligi
agar (n == 1) qaytish;
for( i = 1 ; i <= n ; i + + ) {
74
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
Machine Translated by Google

---

Yuqoridagi funktsiyaning murakkabligi - bu faqat
bir marta bajariladigan break operatori.
// doimiy vaqt
funktsiya ( n-3 );
for( j = 1 ; j <= n ; j + + )
}
}
for( i = 1 ; i <= n ; i + + )
. Ichki pastadir bilan chegaralangan bo'lsa ham, lekin tufayli
}
chop etish ("*" );
tanaffus;
agar (n == 1) qaytish;
funktsiya (int n) {
// ichki sikl faqat vaqt tufayli bajariladi for( j=
1 ; j <= n ; j + + ) {
agar (n == 1) qaytish;
}
agar ( n == 1 )
qaytarilsa; //tashqi tsiklni bajarish vaqtlari
Masala-28
Quyida ish vaqti uchun rekursiv funksiyani yozing. Iterativ usul
yordamida isbotlang
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing. funktsiya ( int n )
{
}
chop etish ("*");
//tashqi tsiklni bajarish vaqtlari
}
funksiya funksiyasining kodi
}
bayonot.
sindirish;
for( i = 1 ; i <= n ; i + + )
// doimiy vaqt
funktsiya ( int n ) {
for( i = 1 ; i <= n ; i + + ) {
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
75
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
Machine Translated by Google

---

.
}
{
Masala-32
Quyidagi kodning ishlash vaqti ekanligini isbotlang
chop etish ("*");
Muammo-29
Takrorlanish munosabati chegaralarini aniqlang:
Masala-33
Quyidagi takrorlanishni yeching.
Muammo-31
Takrorlanish munosabati chegaralarini aniqlang:
for( j = 1 ; j <= n ; j + + )
asosiy teoremani olamiz
bu shuni ko'rsatadi
Yechish: ning qiymati ning qiymatidan katta yoki teng bo‘lganda, while sikli tugaydi. Har bir sikl qiymati ga
ko‘paytirilayotganligi sababli, agar i takrorlashlar soni bo‘lsa, i takrorlashdan keyin 3i qiymatiga ega bo‘ladi. Ya'ni, ÿ n ÿ i ÿ
bo'lganda, i iteratsiyaga erishilgandan so'ng, tsikl tugaydi.
har bir qo'ng'iroqdan beri
konstanta qayerda.
int k = 1;
ba'zi doimiy uchun
Muammo-30
Takrorlanish chegaralarini aniqlang:
Yechish: Bo‘lish va bo‘lib o‘tish bosh teoremasidan foydalanib, biz olamiz
funktsiya (n-3);
O'qish (int n);
,
( )
Yechish: Asosiy teoremadan foydalanib, biz olamiz
// doimiy vaqt
dan foydalanish
//ichki sikl n marta bajariladi
,
}
Yechish: Takrorlanish tenglamasini almashtirsak, biz quyidagilarni olamiz:
Ushbu kodning takrorlanishi aniq T yulduzchalarni
chop etadi va o'zini n - 3 da rekursiv chaqiradi. Iterativ usuldan foydalanib, biz quyidagilarni olamiz:
while( k < n ) k
= 3k;
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
76
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
Machine Translated by Google

---

Ushbu muammo uchun asosiy teorema.
funktsiya (n)
agar (n==0) bo'lsa, 0 ni qaytaring
.
}
{
Fib[n]
,
{
Aks holda Fib[n-1]+Fib[n-2] qaytariladi
for( j = 1 ; j <= n ; j+ = i )
funktsiya (n)
for( i = 1 ; i <= n ; i + + )
agar (n==1) bo'lsa, 1 ni qaytaring
for( i = 1 ; i <= n ; i + + )
//bu sikl n marta bajariladi
Bildirishnomada ikkilik daraxtni ko'rsatadigan ikkita takroriy qo'ng'iroq mavjud. Har bir qadam rekursiv ravishda
kamaytirilgan dasturni chaqiradi va shuning uchun takrorlanish daraxtining chuqurligi Chuqurlikdagi barglar soni,
chunki bu to'liq ikkilik daraxt bo'lib, har bir barg kamida doimiy omil uchun hisoblashni oladi. Ishlash vaqti aniq
eksponentdir
“*”
Muammo-35
Quyidagi dasturning ishlash vaqti?
Yechim: Takrorlash orqali:
Eslatma: Biz foydalanishimiz mumkin
Yechish: Ushbu dasturning ishlash vaqti uchun takrorlanish munosabati
ÿ ÿ
ÿ
chop etish (
Muammo-34
Quyidagi dasturni ko'rib chiqing:
{
);
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
77
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
Machine Translated by Google

---

.
Uning ishlash vaqti
funktsiya (int n)
}
bu muammo ekanligini ko'rishimiz mumkin
“*”
}
qaytish;
for( j = 1 ; j <= n ; j+ = i )
Yechish: ga ekvivalent logarifmik xususiyatdan
foydalanish
//bu sikl qiymatning rekursiv sikli bilan bajariladi
agar (n <= 1)
chunki ichki halqa muammo-23 bilan bir xil].
{
{
Masala-36
ÿ ning murakkabligi nimadan iborat
Masala-37
Quyidagi rekursiv funktsiyaning ishlash vaqti qancha (kirish qiymatining funksiyasi sifatida ko'rsatilgan)? Avval
takrorlanish formulasini yozing va keyin uning murakkabligini toping.
}
Bu vaqt murakkabligini ko'rsatadi
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
for (int i=1 ; i <= 3; i++ ) f( );
ÿ
for (int i=1 ; i <= 3; i++ ) f( );
chop etish ();
?
//bu sikl j marta i ga ortishi bilan bajariladi
agar (n <= 1)
qaytish;
funktsiya (int n)
ÿ
// doimiy vaqt
78
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
Machine Translated by Google

---

// doimiy vaqt
Masala-38
Quyidagi rekursiv funktsiyaning ishlash vaqti nima (funktsiya sifatida ko'rsatilgan
,
quyida. Funktsiyaning ishlash vaqti qancha
(int n) {
doimiy vaqt talab qiladi (
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
.
kimning kodi
}
har bir butun son uchun
(i=1 ; i <= 3 ; i++ ) funksiya
uchun (n - 1).
Masala-39 ning
funksiyasi sifatida ish vaqti uchun rekursiya formulasini yozing?
dan foydalanish
agar (n <= 1)
//bu sikl n-1 qiymatli rekursiv chaqiruv bilan 3 marta bajariladi
takrorlanish:
kirish qiymati? Avval takrorlanish formulasini yozing va uning yechimini induksiya yordamida ko'rsating.
agar (n <= 1)
,
,
Asosiy teoremadan foydalanib, biz olamiz
funktsiya (int n) {
). Bu bilan biz pastadirni e'tiborsiz qoldiramiz va funksiya rekursiv
chaqirilganini faqat uch marta hisoblaymiz. Bu vaqt murakkabligini anglatadi
funksiyasidan
}
The
. Buning uchun takrorlanish
qaytish;
Asimptotik tahlil uchun kod shunday deb taxmin qilishimiz
mumkin
(i=1 ; i <= 3 ; i++ ) funksiya
uchun (n - 1).
asosiy teoremani olamiz
agar (n <= 1)
qaytarilsa;
qaytish;
funktsiya (int n) {
Endi biz vaqtlarni almashtirganda yechimni taxmin qilish uchun takroriy almashtirishdan foydalanamiz:
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
79
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
©www.CareerMonk.com
Machine Translated by Google

---

80
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
ÿ
Asosiy teoremani qo'llash natija beradi
Takrorlanishning murakkabligini toping:
// doimiy vaqt
int i = 1;
// bu sikl vaqtlarni doimiy vaqt sikli bilan bajaradi for(i =
1; i < n; i + +)
print(“*”);
Logarifmni ikkala tomondan qo'llash,
.
funktsiya (0,8n);
( )
Muammo-41
funktsiya (0,8n);
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
Ushbu kod qismining takrorlanishi
.
//doimiy vaqt,
agar (n <=
1) qaytsa;
Masala-40
Takrorlanishning murakkabligini toping:
Buni oddiy qilish uchun biz taxmin qilamiz
Agar biz orqaga almashtirsak,
int i = 1;
Yechish: Berilgan takrorlanish asosiy teorema shaklida emas. Keling, ushbu asosiy teorema formatini aylantirishga harakat
qilaylik. Buning uchun shunday deb faraz qilaylik
}
}
for(i = 1; i < n; i + +)
print(“*”);
// 0,8n bilan rekursiv chaqiruv
Endi berilgan funktsiya shunday bo'ladi:
funktsiya (int n)
{
Asosiy teoremani qo'llash orqali biz olamiz
( )
ÿ
(ÿ )
Machine Translated by Google

---

Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
81
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
©www.CareerMonk.com
.
int funktsiyasi (int n) {
qaytish (Funktsiya (floor(sqrt(n))) + 1);
ÿ
ÿ . Va, bu xuddi shunday
agar ( n < 2 )
boshqa
funktsiya (int n) {
Yechish: 40-Masaladagi mantiqqa o'xshash mantiqni qo'llaymiz va olamiz
Yechish: Masala-40 mantig‘ini qo‘llash natijasida:
int funktsiyasi (int n) {
agar (n <= 2)
)
qaytish 1;
// ÿ + 1 marta bajaradi
Asosiy teoremani qo'llash natija beradi
qaytish;
Yuqoridagi funksiya uchun takrorlanish funksiyasi quyidagicha berilishi
mumkin: Masala-41.
.
Asosiy teorema natijalaridan foydalanish
qaytish (Funktsiya (floor(sqrt(n))) + 1);
.
.
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
}
// doimiy vaqt
Masala-44
Quyidagi rekursiv protseduraning ishlash vaqtini funktsiya sifatida tahlil qiling. bekor
Masala-42
Takrorlanishning murakkabligini toping:
Masala-43
Quyidagi funksiyaning murakkabligini toping.
(
O'rnini bosish
( )
( )
agar (n <= 2)
, beradi
Almashtirish beradi
}
qaytish 1;
boshqa
boshqa
Machine Translated by Google

---

©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
82
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
}
bekor funktsiyasi (int n) {
}
Masala-45
Quyidagi funksiyaning murakkabligini toping.
n =
// doimiy vaqt
temp = 1
.
Asosiy teoremadan foydalanish,
hisoblagich = 0;
uchun i = 1 dan 8 gacha
boshqa
harorat = 1
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
//doimiy vaqt agar
( n < 2 )
qaytsa;
.
takrorlang
funktsiya ( ); //
bu tsikl I =1 bajarish uchun doimiy vaqt tsikli bilan vaqtlarni bajaradi
uchun i = 1 dan n gacha
hisoblagich = hisoblagich + 1;
funktsiya ( );
hisoblagich =
0; // bu tsikl i = 1 dan 8 gacha bo'lgan har bir chaqiruvda n qiymatining yarmi
bilan 8 marta bajariladi.
hisoblagich = hisoblagich + 1;
qilish uchun I =1
takrorlang
Yechim: Quyidagi funktsiyadagi izohlarni ko'rib chiqing va (n) funksiyaning ishlash vaqtiga murojaat qilaylik
quyidagicha belgilash mumkin:
temp = temp + 1;
n <= 1 gacha
Machine Translated by Google

---

©www.CareerMonk.com
Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
83
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
);
chop etish (
Muammo-47
Quyidagi dasturning ishlash vaqti?
Asosiy teoremadan foydalanib, biz olamiz:
for( j = 1 ; j <= n ; j += 4 )
“*”
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
{
chop etish (
// bu sikl n marta bajariladi
Muammo-46
Quyidagi dasturning ishlash vaqti?
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
);
{
{
Yuqoridagi dasturning murakkabligi:
temp = temp + 1;
}
funktsiya (int n)
funktsiya (int n)
n =
for( j = 1 ; j <= n ; j * = 2 )
for( i = 1 ; i <= n ; i + + )
Ushbu funktsiyaning takrorlanishi
“*”
for( j = 1 ; j <= n ; j * = 2 )
for( i = 1 ; i <= n/3 ; i + + )
“*”
);
.
}
for( i = 1 ; i <= n ; i + + )
// bilan rekursiv chaqiruv
uchun i = 1 dan n gacha
funktsiya (int n)
funktsiya (int n)
n <= 1 gacha
chop etish (
// bu tsikl logarifmlarimizdan logn vaqtlarini bajaradi //ko'rsatma
}
{
// bu sikl n marta bajariladi
Machine Translated by Google

---

Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
84
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
©www.CareerMonk.com
funktsiya ();
( )
Masala-48
Quyidagi funksiyaning murakkabligini toping.
// bu sikl n/3 marta bajariladi
{
}
Asosiy teoremadan foydalanib, biz olamiz
qaytish;
bekor funktsiyasi (int n)
{
// bu sikl n/4 marta for( j = 1 ; j <= n ;
j += 4) bajariladi.
“*”
{
//doimiy vaqtni
chop etish
("*"); //n/2 qiymatli funksiya
bilan rekursiya ( n/
2 ); //n/2 qiymatli funksiya bilan
rekursiya ( n/2 );
Ushbu dasturning vaqt murakkabligi
funktsiya ();
}
Ushbu funktsiyaning takrorlanishi:
bekor funktsiyasi (int n)
}
agar (n > 1)
chop etish ();
for( i = 1 ; i <= n/3 ; i + + )
agar(n <= 1)
Yechim: Quyidagi funksiyadagi izohlarni ko‘rib chiqing:
}
chop etish ("*");
}
Masala-49
Quyidagi funksiyaning murakkabligini toping.
//doimiy vaqt if(n
<= 1)
qaytish;
agar (n >
1) {
Machine Translated by Google

---

Ma'lumotlar tuzilmalari va algoritmlari osonlashtirildi
85
Algoritmlar tahlili | Algoritmlarni tahlil qilish masalalari
©www.CareerMonk.com
int j=n;
esa (i < n) {
} // i
i=2*i; // kirish vaqtlari
i=2*i;
while(j > 0) j
= j/2; logn kodi ..
funktsiya()
Yechim:
}
}
} // i
{
.
int i=1;
{
esa (i < n) {
funktsiya()
int i=1;
Vaqtning murakkabligi:
while(j > 0) j
= j/2;
int j=n;
Machine Translated by Google

---