سوال اول: 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 باشه یعنی:
و جواب آخر هم بشه

تو اینایی که نوشتی فاکتوریل داری؟

نفهمیدم... :|

نه علامت تعجب آخر جمله بود که اصلاح شد.

مرسی واسه اصلاح.

من کلا نفهمیدم

یواش تر بگو یکم اگه ممکنه.

کجاشو متوجه نشدید؟
من کلا توی توضیح دادن مشکل دارم ، ولی اینبار تمام سعیمو کردم که خوب توضیح بدم، نشد!
هرجا که متوجه نشدید بگید تا من بیشتر توضیح بدم.

سلام
من فکر میکنم سری اول اینجوری حل میشه
این سری دو قسمت هست همه جملات 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

سلام دوست عزیز واسه سوال اول من این راه و رفتم
برای بار اول که 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 کلا تو عبارت اول ۲۴ بار اجرا میشه و عبارت دوم ۱۶ بار ! درسته!!!؟؟؟؟!