(۲۷ مرداد ۱۳۹۲ ۱۱:۱۰ ب.ظ)SnowBlind نوشته شده توسط:  سلام

من با هیچ روشی نمتونم بفهمم مرتبه ی این کد چی میشه و کلا اعصابمو ریخته به هم

کد php:

i = n;
while(i >= 1) {
    j = i;
    while(j <= n) {
        j *= 2;
    }
    i /= 2;
} 


کسی میتونه راه نمایی کنه؟

به ازای i=n حلقه داخلی ۱بار میچرخد و به ازای i=n/2 حلقه داخلی ۲بار میچرخد و به ازای i=n/4 حلقه داخلی ۳بار میچرخد و به ازای i=n/8 حلقه داخلی ۴بار میچرخد و ... و اگر با هوش باشید مثل من (محض تنوع) متوجه خواهیم شد که به ازای i=1 حلقه داخلی logn+1 بار میچرخد
حالا جمع تصاعدی بزن:
میدانیم:
[tex]1 2 ... n=n(n 1)/2[/tex]
پس:
[tex]1 2 ... (logn 1)=(logn 1)(logn 2)/2=O(log^{2}n)[/tex]

من یه چیزی به ذهنم رسیده.
حلقه خارجی مرتبه زمانی [tex]O(lgn)[/tex] هست.
مرتبه زمانی حلقه داخلی با عوض شدن i و در نهایت j به این صورت هست. [tex](1 2 ... lgn)[/tex]
که یه تصاعد عددی محسوب میشه که مجموع جملات برابر هست با ([tex]\frac{lg*n .(lgn 1))}{2}[/tex]).
پس نظر من اینه که اردر کلی برابر است با [tex]O(lg*n . (lgn)^{2})[/tex].
البته اصلا به این جواب مطمئن نیستم لطفا بقیه دوستان هم بیاند نظر بدند.

---

(۲۸ مرداد ۱۳۹۲ ۱۲:۳۸ ق.ظ)M4$0UD نوشته شده توسط:  من یه چیزی به ذهنم رسیده.
حلقه خارجی مرتبه زمانی [tex]O(lgn)[/tex] هست.
مرتبه زمانی حلقه داخلی با عوض شدن i و در نهایت j به این صورت هست. [tex](1 2 ... lgn)[/tex]
که یه تصاعد عددی محسوب میشه که مجموع جملات برابر هست با ([tex]\frac{lg*n .(lgn 1))}{2}[/tex]).
پس نظر من اینه که اردر کلی برابر است با [tex]O(lg*n . (lgn)^{2})[/tex].
البته اصلا به این جواب مطمئن نیستم لطفا بقیه دوستان هم بیاند نظر بدند.

الان که یکم فکر کردم به نظرم غلطه
فکر کنم جواب [tex]lg*n(lgn)[/tex] باشه. حالا بقیه لطفا نظر بدند تا با هم بحث کنیم.

ممنون از دوستان فکر کنم جواب دوستمون مجید جواب درست هستش، در ضمن این تمرین کتاب ساختمان داده پیام نور بود.

حق با شماست من خنگ را بگو فکر کردم تعداد جمله های تصاعد lg*n میشه (امان از جو گیر شدن)
من برم تو افق محو شم