سلام.
دوستان محبت میکنین این رو حل کنید؟
اولیش اینه:
[tex]for(i=1;i<n;i*=2)[/tex]
[tex]for(j=i;j<n;j )[/tex]
ببینید، من اینو رفتم جلو تا رسیدم به این:
[tex]n (n-2) (n-4) (n-8) ... (n-2^k)[/tex]
سواد ریاضیم نمیکشه از این جلوتر برم.
دومی هم اینه:
[tex]for(i=1;i<n;i*=2)[/tex]
[tex]for(j=1;j<i;j )[/tex]
ممنونم از همگی.
سوال اول: lgn تا جمله ی دارای n هست که میشه nlgn.
سوال دوم هم که سادس چندتا از دنبالشو مینویسیم که میشه
[tex]1 2 4 ... n/2[/tex]
برای سادگی فرض میکنیم که n توانی از ۲ست(چون هر بار i ضرب در ۲ میشه ، پس حلقه نهایتا با یه عدد که توانی از ۲ست به پایان میرسه و ما برای سادگی محاسبات فرض میکنم که n دقیقا همون عدده!) یعنی [tex]n=2^k[/tex] که در کل اون رابطه برابر میشه با :
[tex]1 2 4 ... 2^k/2=1 2 4 ... 2^{k-1}[/tex] و این یه تصاعد هندسیه و برابره با:
[tex]2^{k-1 1}-1=2^k-1=n-1[/tex] البته اگر n توانی از ۲ باشه! اگه نباشه جواب میشه [tex]2^{\left \lceil lgn \right \rceil}-1[/tex] .
تو اینایی که نوشتی فاکتوریل داری؟
نفهمیدم... :|
نه علامت تعجب آخر جمله بود که اصلاح شد.
مرسی واسه اصلاح.
من کلا نفهمیدم
یواش تر بگو یکم اگه ممکنه.
کجاشو متوجه نشدید؟
من کلا توی توضیح دادن مشکل دارم ، ولی اینبار تمام سعیمو کردم که خوب توضیح بدم، نشد!
هرجا که متوجه نشدید بگید تا من بیشتر توضیح بدم.
سوال دوم هم که سادس چندتا از دنبالشو مینویسیم که میشه
[tex]1 2 4 ... n/2[/tex]
سلام
به نظرتون نباید دنبالش تا logn باشه یعنی:
۱+۲+۳+۴+...+logn
و جواب آخر هم بشه O(log^2 n)
سلام
من فکر میکنم سری اول اینجوری حل میشه
این سری دو قسمت هست همه جملات n دارند پس میشه n ها را جدا کرد
بقیه عبارت(۱و۲و۴) هم سری هندسی با قدرنسبت ۲ هست
[tex]n (n-2) (n-4) (n-8) ... (n-2^k)=(n n n ....)-(2^{0} 2^{1} 2^{2}...2^{k})=(nk)-(\frac{2^{0}(2^{k}-1)}{1-2}) \simeq nk[/tex]
خب حالا k هم که میشه logn
پس مرتبه زمانی میشه
nlogn
(۰۶ بهمن ۱۳۹۱ ۰۳:۲۸ ق.ظ)slinda نوشته شده توسط: سوال دوم هم که سادس چندتا از دنبالشو مینویسیم که میشه
[tex]1 2 4 ... n/2[/tex]
سلام
به نظرتون نباید دنبالش تا logn باشه یعنی:
۱+۲+۳+۴+...+lognو جواب آخر هم بشهO(log^2 n)
سلام نه دیگه
هر بار عدد ضرب در ۲ میشه و اگر n توانی از ۲ باشه چون شرط حلقه مساوی نداره پس حتما تا n/2 پیش میره !
تست کردن جواب کار ساده ایه فقط لازمه یه عدد به جای n بذارید و از روی حلقه تعداد اجراشو حساب کنید و بعد n رو توی رابطه [tex]2^{\left \lceil lgn \right \rceil}-1[/tex] قرار بدید.
مثلا اگر فرض کنیم که n=17، حلقه داخلی در کل ۳۱ بار اجرا میشه . خوب [tex]\left \lceil lg 17 \right \rceil[/tex] هم که ۵ میشه و [tex] 2^5 -1=31[/tex].
درست نیست؟
هر عددی بین ۱۶ تا ۳۱ که جای n بذاریم جوابش همینه!
سلام دوست عزیز واسه سوال اول من این راه و رفتم
برای بار اول که i=1 هستش حلقه دوم n بار میچرخه یعنی تا اینجا میدونیم که n بار رو داره
ولی برای ادامه اگ دقت کنیم دفه بعدی i=2 شده و دوباره حلقه دوم n بار میچرخه
برای بار سوم i=4 و دوباره n بار میچرخه و به همین حالت تا وقتی که i=n بشه
یعنی برای n=4 این حلقه ۳n بار اجرا میشه
برای n=8 این حلقه ۴n بار اجرا و میشه
و برای n=2^k این حلقه
[tex]n\left ( \left ( log 2^k \right ) 1 \right ))k=\left ( log n \right )[/tex]
پس کلا داریم n logn
برای دومی هم برای بار اول ۱ بار
بار دوم یعنی وقتی i=2 میشه ۲ بار و وقتی i=4 میشه ۴ بار و .....
تا وقتی که i=n بشه
خوب بازم فرض و میذاریم روی n=2^k که داریم [tex]n\left ( \left ( log 2^k \right )-1 \right ))[/tex]
که بازم k=log n هستش این بار هم n log n میشه اگ با دو تا عدد مثال بزنی هم دستت میاد چی میگم برای n=8 کلا تو عبارت اول ۲۴ بار اجرا میشه و عبارت دوم ۱۶ بار ! درسته!!!؟؟؟؟!