سلام. مطمئن نیستم درست باشه :|
trace می کنیم.
در ابتدا : Dec=0
در حلقه ی اول:
i=0 … j=1 … [tex]l=power(2,i)=2^0=1[/tex]
چون j=l هست پس شرط while یه بار درست هست و داخلش اجرا میشه.
درون while :
s=1 … ++dec
s=4 … ++dec
s=7 … ++dec
s=10 … ++dec
.
.
s=n*n … ++dec
در انتهای while : j=j*2=2
چند بار ++dec انجام شده؟ از ۱ تا n به توان ۲ با گام ۳ : [tex]\frac{n^2}{3}[/tex]بار تقریبا
------------------------------------------------------------------------------------
i=1 … j=1 … [tex]l=power(2,i)=2^1=2[/tex]
شرط while در ابتدا درست هست که j=1 و l=2 شده.
درون while :
s=1 … ++dec
s=4 … ++dec
s=7 … ++dec
s=10 … ++dec
.
.
s=n*n … ++dec
در انتهای while : j=j*2=2.
چند بار ++dec انجام شده؟ از ۱ تا n به توان ۲ با گام ۳ : [tex]\frac{n^2}{3}[/tex]بار تقریبا
حالا j=2 شده و l هم که درست هست، پس یه بار دیگه شرط while درست هست و داریم:
درون while :
s=1 … ++dec
s=4 … ++dec
s=7 … ++dec
s=10 … ++dec
.
.
s=n*n … ++dec
در انتهای while : j=j*2=2.
چند بار ++dec انجام شده؟ از ۱ تا n به توان ۲ با گام ۳ : [tex]\frac{n^2}{3}[/tex]بار تقریبا
------------------------------------------------------------------------------------
i=2 … j=1 … [tex]l=power(2,i)=2^2=4[/tex]
شرط while دفعه ی اول که j=1 هست، دفعه ی دوم که j=2 میشه و دفعه ی سوم که j=4 میشه درست هست چون از l کوچیکتر هست. پس سه بار داخل حلقه ی while اجرا میشه.
------------------------------------------------------------------------------------
i=3 … j=1 … [tex]l=power(2,i)=2^3=8[/tex]
شرط while دفعه ی اول که j=1 هست، دفعه ی دوم که j=2 میشه و دفعه ی سوم که j=4 میشه و دفعه ی چهارم که j=8 میشه درست هست چون از l کوچیکتر هست. پس چهار بار داخل حلقه ی while اجرا میشه.
------------------------------------------------------------------------------------
i=4 … j=1 … [tex]l=power(2,i)=2^4=16[/tex]
شرط while دفعه ی اول که j=1 هست، دفعه ی دوم که j=2 میشه و دفعه ی سوم که j=4 میشه و دفعه ی چهارم که j=8 میشه و دفعه ی پنجم هم درست هست چون از l کوچیکتر هست. پس پنج بار داخل حلقه ی while اجرا میشه.
خب پس به ازای هر i اون حلقه ی while به اندازه ی [tex]\log l\: +1[/tex] بار انجام میشه و هر بار هم هزینه ش میشه [tex]\theta(n^2)[/tex]
[tex]l=2^i[/tex]
[tex]\sum^{n-1}_{i=1}\log2^i+1[/tex] بار حلقه ی while اجرا میشه که هر بار هزینه ش [tex]\theta(n^2)[/tex] هست.
پس کل هزینه و مقدار نهایی dec میشه : [tex]n^2\times\sum^{n-1}_{i=1}\log2^i+1=n^2\times\sum_{i=1}^{n-1}i+1=n^2\times[2+3+...+n]=\theta(n^4)[/tex]