سلام
با اجازه سوال اول رو توضیح میدم.

ببینید بعد از for اول یک اکولاد باز شده و تمام دستورات بعدش داخل اکولاد هست. بیایید با یک مثال حلش کنیم. فرضا n برابر ۳ باشه.
باید با n برابر ۳ برنامه رو دنبال کنیم.
ابتدا در حلقه اول هستیم. i برابر یک میشه و سپس شرط i<=n چک میشه. شرط برقراره؟ بله چون i که همون یک باشه از n که ۳ است کمتره. پس دستورات پایین حلقه اجرا میشه.
وارد حلقه دوم میشیم. j رو برابر یک میکنه و سپس شرط j<=n اجرا میشه. و شرط برقراره. خوب وارد دستورات پایین میشه. این رو می دونیم که در حلقه for فقط یک دستور پایین حلقه اجرا میشه. وای اگه اکولاد داشته باشه تمام دستورات داخلش اجرا میشن. خوب الان می بینیم که فقط یک دستور پایین از حلقه دوم باید اجرا بشه. دستور $x=x 1$ اجرا میشه و از دوباره وارد حلقه دوم میشه و j=2 میشه شرط حلقه چک میشه و دستور $x=x 1$ دوباره اجرا میشه و j همین طور بهش اضافه میشه تا به n برسه که در مثال ما ۳ بود. دیگه از حلقه دوم خارج میشه. خوب حالا وارد دستور پایین یعنی $n=n-1$ میشه و n کم میشه.
خوب پس حالا وارد حلقه اول میشه. و به i اضافه میشه و همین روال دوباره تکرار میشه.
ولی نکته چیه؟
در مرحله اول حلقه n بار اجرا میشه.
در مرحله دوم n-1 بار
در مرحله سوم n-2 بار
در مرحله چهارم n-3 بار
....
و در اخر هم یکبار
خوب مجموعا چند بار اجرا شد؟ ۱+...+n(n+1)/2=n+n-1+n-2+n-3
پس ار مرتبه n به توان ۲ میشه.

ببینید برای یادگرفتن این طور سوال ها کافیه که یک مثال برای n بزنید و حلش کنید.

(۲۴ تیر ۱۳۹۱ ۱۰:۳۶ ب.ظ)Aurora نوشته شده توسط:  در مرحله اول حلقه n بار اجرا میشه.
در مرحله دوم n-1 بار
در مرحله سوم n-2 بار
در مرحله چهارم n-3 بار
....
و در اخر هم یکبار
خوب مجموعا چند بار اجرا شد؟ ۱+...+n(n+1)/2=n+n-1+n-2+n-3
پس ار مرتبه n به توان ۲ میشه.

ببخشید روی تست اول من یه سوال دارم:
مگه حلقه مربوط به i تا n/2 پیش نمیره؟
یعنی بار اول حلقه j دقیقا n بار اجرا میشه و بعد n یکی کم میشه
بار دوم حلقه j دقیقا n-1 بار اجرا میشه و n یکی دیگه کم میشه و بهمین ترتیب
منتها چون n داره کم میشه مقدار i تا n/2+1 پیش میره
یعنی کل دفعات اجرا میشه n+(n-1)+(n-1)+...+(n/2+1) ؟

اولی از مرتبه nبه توان ۲ ,و دومی از مرتبه n هستش. به کروشه ها دقت کن. هنگامی که بعد از for کروشه نیاد فقط یک دستور سطر پایینشو اجرا میکنه.

(۲۴ تیر ۱۳۹۱ ۱۲:۳۳ ب.ظ)ghaderiyaser نوشته شده توسط:  اولی از مرتبه nبه توان ۲ ,و دومی از مرتبه n هستش. به کروشه ها دقت کن. هنگامی که بعد از for کروشه نیاد فقط یک دستور سطر پایینشو اجرا میکنه.

ببین من منظورتو متوجه نمی شم می خوام کلاً بدونم چجوری چه این و چه حالت دیگه مرتبه زمانی را باید حساب کنم همین فعلاً جواب نمی خوام راه حل می خوام اونم به زبان ساده اول ابتدایی

(۲۴ تیر ۱۳۹۱ ۰۳:۰۸ ب.ظ)naderx نوشته شده توسط:  تست اول رو گوش کن اگه واضح بود بگو دومی رو شروع کنم.

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

ممنون بابت توضیحات ، ولی شما تست دوم اول گفتید

بله درسته. این قسمت اخر رو اشتباه کردم. ممنون از شما جهت یاداوری.دوستان معذرت بابت اشتباه.
چون i و n هر دو همزمان با هم در حال تغییرند تا n=1 پیش نمیره . یعنی i یکی یکی بهش اضافه میشه و n هم یکی یکی ازش کم میشه. تا اینکه تقریبا در وسط به هم برسند.
شکلشو برای n= 3 کشیدم.


الان درسته؟

بله درسته. ممنونم که کامل پاسخ دادید.

در مورد تست دوم هم من یکجایی رو متوجه نمیشم. ممنون میشم شما یا دوستان توضیح بدید.
بنظرم اون فایل صوتی و عکسی که همراهش هست، کاملا درسته منتها اون عبارت داخل پرانتز چرا تا بینهایت پیش میره؟
جالبه که تو پوران هم همینکارو کرده. البته به لحاظ پیچیدگی فرقی نمیکنه اما اگر تعداد دقیق دفعات اجرای x++ را بخواهیم فکر نکنم درست باشه.
یعنی مثلا اگر n=8 باشه:
برای i=1 حلقه j دقیقا ۸/۲=۴ بار تکرار میشه و مقدار n هم میشه ۴/
برای i=2 حلقه j دقیقا ۴/۲=۲ بار تکرار میشه و n هم میشه ۲/
برای i=3 حلقه j دقیقا ۲/۲=۱ بار تکرار میشه و n هم میشه ۱/
و برای i=4 حلقه j یکبار دیگه تکرار میشه چون شرط j<=1 برقراره و n میشه ۰ و دیگه حلقه j تکرار نمیشه.
بنابراین تعداد دفعات اجرای x++ میشه:
n/2 + n/4 + n/8 + ... + n/2^k + 1
طوریکه k=logn هست. یعنی اون سری تا بینهایت نمیره که بگیم میشه سری هارمونیک و کلش برابر با ۱ ؟
درواقع میشه:
n[1/2+1/4+1/8+....+1/n]+1
که داخل پرانتز هم میشه:
$\frac{1}{2}\times \frac{(\frac{1}{2})^{log n}-1}{\frac{1}{2}-1} =\frac{n-1}{n}$
و کل زمان اجرا:
$n-1 1=n$
؟؟