Sikllarni analiz qilish

Sikllarni analiz qilish
Bu mustaqil ishda iterativ dasturlarni oddiy misollar bilan tahlil qilish muhokama qilinadi.
Misol uchun swap() funkisyasi O(1) vaqt murakkabligiga ega.
1)O(1):Doimiy marta bajariladigan sikl yoki rekursiya ham O(1) deb hisoblanadi. Masalan, quyidagi tsikl O(1) dir.
// Bu yerda c o’zgarmas
for (int i = 1; i <= c; i++)
2) O(n): Agar tsikl oʻzgaruvchilari doimiy miqdorga oshirilsa/kamaytirilsa, siklning vaqt murakkabligi O(n) deb hisoblanadi. Masalan, quyidagi funktsiyalar O(n) vaqt murakkabligiga ega.
// Bu yerda c musbat butun son doimiysi
for (int i = 1; i <= n; i += c) {
}
for (int i = n; i > 0; i -= c)
// ba'zi O(1) ifodalar
3) O(n^с): Ichki tsikllarning vaqt murakkabligi eng ichki bayonot bajarilish soniga teng. Masalan, quyidagi namunali tsikllar O(n²) vaqt murakkabligiga ega.
for (int i = 1; i <=n; i += c) {
for (int j = 1; j <=n; j += c) {
// ba'zi O(1) ifodalar
}
}
for (int i = n; i > 0; i -= c) {
for (int j = i+1; j <=n; j += c) {
// ba'zi O(1) ifodalar
}
Masalan, Tanlash tartibi va Qo‘shish tartibida O(n²) vaqt murakkabligi mavjud.
4) O(Logn):Vaqti siklning murakkabligi O(Logn) deb hisoblanadi, agar sikl o'zgaruvchilari doimiy miqdorga bo'linadi/ko'paytirilsa. Shuningdek, rekursiv funktsiyada rekursiv chaqiruv uchun Vaqt murakkabligi O (Logn) sifatida qabul qilinadi.

for (int i = 1; i <=n; i *= c) {
// ba'zi O(1) ifodalar }
for (int i = n; i > 0; i /= c) {
// ba'zi O(1) ifodalar }
//Rekursiv funkisya
void recurse(n)
{
if(n==0)
return;
else{
// ba'zi O(1) ifodalar }
recurse(n-1);
}
Masalan, Binary Search (iterativ dasturga murojaat qiling) O(Logn) vaqt murakkabligiga ega. Keling, qanday qilib O (Log n) ekanligini matematik jihatdan ko'rib chiqaylik. Birinchi tsiklda biz oladigan qator 1, c, c2, c3, … ck. Agar k ni Log_n^c ga teng qo'ysak, c^Log_cⁿ ni olamiz, ya'ni n.
5)O(LogLogn):Vaqt murakkabligi siklning o'zgaruv- chilar doimiy miqdorga eksponent ravishda kamayti- rilsa/ko'paytirilsa, O(LogLogn) deb hisoblanadi
// Bu yerda c 1 dan katta doimiydir
for (int i = 2; i <=n; i = pow(i, c)) {
// ba'zi O(1) ifodalar
}
//Bu yerda qiziqarli sqrt yoki cuberoot yoki boshqa har qanday doimiy ildiz

for (int i = n; i > 1; i = fun(i)) {
// ba'zi O(1) ifodalar
}
Matematik tafsilotlar uchun buni ko'ring.
Ketma-ket tsikllarning vaqt murakkabligini qanday birlashtirish mumkin?
Ketma-ket tsikllar mavjud bo'lganda, biz vaqt murakkabligini individual halqalarning vaqt murakkabliklari yig'indisi sifatida hisoblaymiz.
for (int i = 1; i <=m; i += c) {
// ba'zi O(1) ifodalar
}
for (int i = 1; i <=n; i += c) {
// ba'zi O(1) ifodalar

}
Yuqoridagi kodning vaqt murakkabligi O(m) + O(n) O(m+n)
Agar m == n bo'lsa, vaqt murakkabligi O(2n) ga aylanadi, bu O(n).

Looplar ichida ko'p if, else iboralari mavjud bo'lganda vaqt murakkabligini qanday hisoblash mumkin?

Bu erda muhokama qilinganidek, eng yomon vaqt murakkabligi eng yaxshi, o'rtacha va eng yomoni orasida eng foydali hisoblanadi. Shuning uchun biz eng yomon holatni ko'rib chiqishimiz kerak. Biz if-else shartlaridagi qiymatlar eng ko'p sonli ko'rsatmalar bajarilishiga olib keladigan vaziyatni baholaymiz.
Misol uchun, chiziqli qidiruv funktsiyasini ko'rib chiqing, bu erda element oxirida mavjud bo'lgan yoki umuman mavjud bo'lmagan holatni ko'rib chiqamiz.
Agar kod barcha if-else holatlarini ko'rib chiqish uchun juda murakkab bo'lsa, biz if-else va boshqa murakkab boshqaruv bayonotlariga e'tibor bermaslik orqali yuqori chegarani olishimiz mumkin.
Oldingi maqolada biz looplarni tahlil qilishni muhokama qildik. Ko'pgina algoritmlar tabiatan rekursivdir. Biz ularni tahlil qilsak, vaqt murakkabligi uchun takrorlanish munosabatini olamiz. Biz n o'lchamdagi kirishda n funktsiyasi sifatida ish vaqtini va kichikroq o'lchamdagi kirishlarda ishlash vaqtini olamiz. Masalan, Merge Sort dasturida berilgan massivni saralash uchun biz uni ikki yarmiga ajratamiz va jarayonni ikki yarmi uchun rekursiv takrorlaymiz. Nihoyat, biz natijalarni birlashtiramiz. Birlashtirish Saralashning vaqt murakkabligi T(n) = 2T(n/2) + cn shaklida yozilishi mumkin. Ikkilik qidiruv, Xanoy minorasi va boshqalar kabi ko'plab boshqa algoritmlar mavjud.Qaytalanishni hal qilishning asosan uchta usuli mavjud.
1)Almashtirish usuli: Biz yechim uchun taxmin qilamiz va keyin taxminning to'g'ri yoki noto'g'riligini isbotlash uchun matematik induksiyadan foydalanamiz.
Masalan, T(n) = 2T(n/2) + n takrorlanishini ko'rib chiqamiz.Biz yechimni T(n) = O(nLogn) deb taxmin qilamiz. Endi biz induksiyadan foydalanamiz taxminimizni isbotlash uchun.T(n) <= cnLogn ekanligini isbotlashimiz kerak. Biz buni haqiqat deb taxmin qilishimiz mumkin.n dan kichik qiymatlar uchun:


T(n) = 2T(n/2) + n
<= 2cn/2Log(n/2) + n
= cnLogn - cnLog2 + n
= cnLogn - cn + n
<= cnLogn
2) Qaytalanish daraxti usuli: Bu usulda biz takrorlanish daraxtini chizamiz va daraxtning har bir sathi uchun olingan vaqtni hisoblaymiz. Nihoyat, biz barcha darajadagi bajarilgan ishlarni jamlaymiz. Qaytalanish daraxtini chizish uchun biz berilgan takrorlanishdan boshlaymiz va darajalar orasida naqsh topgunimizcha chizishni davom ettiramiz. Naqsh odatda arifmetik yoki geometrik qatordir.
Masalan, takrorlanish munosabatini ko'rib chiqamiz.


T(n) = T(n/4) + T(n/2) + cn²
cn^{2
/ \
T(n/4) T(n/2)}

Agar T(n/4) va T(n/2) ifodalarini yana buzsak,biz quyidagi rekursiya daraxtini olamiz.

cn²
/ \
c(n²)/16 c(n²)/4
/ \ / \
T(n/16) T(n/8) T(n/8) T(n/4)
Keyinchalik parchalash bizga quyidagini beradi
cn²
/ \
c(n²)/16 c(n²)/4
/ \ / \
c(n²)/256 c(n²)/64 c(n²)/64 c(n²)/16
T(n) qiymatini bilish uchun daraxt yig‘indisini hisoblashimiz kerak.Tugunlar darajasi bo'yicha. Agar yuqoridagi daraxt darajasini daraja bo'yicha jamlasak,
biz quyidagi seriyani olamiz.T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ....
Yuqoridagi qator 5/16 nisbatda geometrik progressiyadir.Yuqori chegarani olish uchun biz cheksiz qatorni yig'ishimiz mumkin.Biz yig'indini (n²)/(1 - 5/16) sifatida olamiz, bu O(n²).
3) Asosiy usul: Asosiy usul - bu yechimni olishning to'g'ridan-to'g'ri yo'li. Asosiy usul faqat keyingi turdagi takrorlanishlar yoki keyingi turga aylantirilishi mumkin bo'lgan takrorlashlar uchun ishlaydi.


T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

Quyidagi uchta holat mavjud:

1. Agar f(n) = O(n^c) bu yerda c < Log_b^a, u holda T(n) = ʘ(n^Log_b^a)

2. Agar f(n) = ʘ(n^c) bunda c = Log_b^a bo'lsa, T(n) = ʘ(n^c Log n) bo'ladi.

3.Agar f(n) = Ω ( n^c) bunda c > Log_b^a bo'lsa, T(n) = ʘ(f(n)) bo'ladi.