پیرو فرمایشات دوستان من هم یه چیزایی میگم:

اولین سوال که همونطور که نوشتید یه تصاعد حسابی هست که جمله اولش برابر n و جمله آخرش برابر ([tex]n- \frac{n}{2} 1[/tex]) و برای محاسبه تصاعد حسابی باید جمله اول و آخر رو جمع کنید و در [tex]\frac{n}{2}[/tex] ضرب کنید (که n تعداد جملات تصاعد است و در اینجا برابر است با [tex]\frac{n}{2}[/tex] که در کل میشود [tex]\frac{n}{4}[/tex])!
جمله آخر که در واقع برابر است با [tex]\frac{2n -n 2}{2}[/tex] که همون [tex]\frac{n 2}{2}[/tex] است و بعد از جمع با n برابر میشه با [tex]\frac{3n 2}{2}[/tex] و بعد از ضرب در [tex]\frac{n}{4}[/tex] میشه همون که شما گفتید.



سوال ۲ :
این هم مثل سوال قبل اگه هر مرحله تعداد اجرای جمله اصلی رو در نظر بگیرید میشه همون [tex]\frac{n}{2} \frac{n}{4} ...[/tex] وقتی از n فاکتور بگیریم به [tex]n(\frac{1}{2} \frac{1}{4} ...)[/tex] میرسیم . خوب جمله داخل پرانتز یه تصاعد هندسی با جمله اول [tex]\frac{1}{2}[/tex] و قدرنسبت [tex]\frac{1}{2}[/tex] است و برای محاسبه تصاعد هندسی وقتی که جملات کوچکتر از ۱ هستند و تعداد آنها بینهایت است از فرمول :
جمله اول تقسیم بر ۱منهای قدر نسبت استفاده میکنیم. که در این سوال میشه [tex]\frac{\frac{1}{2} }{1-\frac{1}{2} }[/tex] که برابر با ۱ است و n*1 بدست می آید.

سوال ۳:
حلقه داخلی با گام i هست که در اون صورت داریم :
دور اول چون i برابر ۱ هست حلقه داخلی n بار اجرا میشه دور دوم چون i برابر ۲ است حلقه داخلی با شمارنده فرد اجرا میشود(۱و۳و۵و...n) (که میشه [tex]\frac{n}{2}[/tex]بار) و به همین ترتیب تا آخر . که در کل میشه [tex]n \frac{n}{2} \frac{n}{3} ...[/tex] و با فاکتور گرفتن از n بدست میاد [tex]n(1 \frac{1}{2} \frac{1}{3} ...)[/tex] که [tex](1 \frac{1}{2} \frac{1}{3} ...)[/tex] تقریبا برابر با [tex]Lg(n)[/tex](نه دقیقا اما در کل میشه گفت که هم رشد هستند) پس در کل میگیم این الگوریتم از مرتبه [tex]\Theta( nlgn)[/tex].

ارزش دانلود داره

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.