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

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



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

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

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

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