(۲۷ خرداد ۱۳۹۱ ۰۲:۰۰ ق.ظ)afagh1389 نوشته شده توسط:  شما هر بار که به حلقه for می رسید اون رو n بار اجرا می کنید و هر بار فقط یک عمل جمع انجام میدین ، یعنی یک بار به ازای j=1 یکبار به ازای j=2 و .... یعنی دارید :
[tex]\sum_{j=1}^{n-1} 1=n-1[/tex]

هر بار که وارد حلقه while می شید هم for رو اجرا می کنید و هم یک عمل ضرب ، اما چه زمانی وارد حلقه while می شید ؟
ازi=1 و هر بار i*3 میشه تا حداکثر به n برسید. یعنی [tex]\left \lfloor \log n \right \rfloor[/tex] بار (در مبنای ۳)

میتونید n=8 بگیرید تا دلیل حدپایین گذاشتن رو متوجه بشید.

چون i هر بار ۳ برابر میشه نمیشه با سیگما نشونش داد پس من از متغیر k استفاده کردم.

که k=logn در مبنای ۳ هست و در نتیجه i=3^k

[tex]\sum_{k=0}^{\left \lfloor logn \right \rfloor-1}[/tex] بار عملیات داخل while تکرار میشه :

[tex]\sum_{k=0}^{\left \lfloor log n \right \rfloor -1} ( \sum_{j=1}^{n-1}1 1)=(\left \lfloor log n \right \rfloor((n-1) 1))=\left \lfloor log n \right \rfloor(n)[/tex]

سلام
مرسی توضیحاتتون خیلی خوب بود.فقط یه راهنمایی میخواستم از شماک این که تو توضیحاتتون از نمادهای ریاضی مثل سیگما وتوان استفاده کردین ولی راستش من هر کاری میکردم نمی تونستم اینجا بنویسمشون ، همه چی بهم می ریخت ، واسه همین اونارو توی word نوشتم وبعد attach کردم.

-------------------------------

حالا اگه مثلا حلقه for به جای j<n بود j<=i اونوقت اندیس سیگمای درونی وابسته میشد به اندیس سیگمای بیرونی.

[tex]\sum_{k=0}^{\left \lfloor log n \right \rfloor-1}( \sum_{j=1}^{3^{k}}1 1)[/tex]