دوستان توی مبحث آنالیز زمانی واقعا ممنون میشم کمکم کنید
سپاسگزارم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام. مطمئن نیستم درست باشه :|
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]