سلام (داستان یک شاگرد شوت و یک استاد با حوصله)
حلقه فور اولی رو بیخیال شو ، پس اول برو سراغ دو تا حلقه فور پاینی، اوکی ؟
خوب چرا این کارو کردیم ؟ چون حلقه اول کاری به دو تا حلقه بعدی نداره یعنی واسه خودش مستقله
مستقل بودن یعنی چی ؟ یعنی این که اندیس حلقه اول که همان i هست داخل حلقه های دیگه وجود نداره
آقا اجازه ؟ بله بفرما ، پس میشه گفت چون اندیس حلقه دوم توی حلقه سوم هست ( j ) پس حلقه سوم و دوم به هم وابسته هستند ؟
بله درست گفتی ! آفرین
حالا بریم ادامه کار ....
قبول داری حلقه دوم اینجوری میشمارد : ۱ بعد ۲ بعد ۴ بعد ۸ بعد ۱۶ و الی آخر ؟
بله قبول دارم
حالا که قبول داری،اینم قبول داری که حلقه سوم به اندازه مقدار اندیس حلقه دوم اجرا میشه ؟
نه قبول ندارم ! یعنی نمیفهمم چی میگین !
بترکی ! آی کیو اندازه جلبک دریایی ! باشه یکم آسون تر میگم :
توی حلقه سوم متغییرش چیه ؟ مگه k نیست ؟ بله، خوب مگه از یک شروع نشده ؟ بله ، خوب جونت در بیاد ! مگه تا j پیش نمیره ؟
بله پیش میره ، خوب پس قبول داری حلقه سومی به اندازه j دستور زیرش رو اجرا میکنه ؟
بزار فکر کنم آهان ! قبول ! ، خوب مگه نگفتی حلقه دوم اینجوری میشمارد : ۱ بعد ۲ بعد ۴ بعد ۸ بعد ۱۶ و الی آخر ؟ بله گفتم ، خوب پس حلقه سوم به ازای هر مقداری که j میگیرد دستور زیرش رو اجرا میکنه ، یعنی : وقتی j یک است یکبار اجرا میکنه و وقتی j
دو است دوبار اجرا میکنه و الی آخر ، یعنی : ۱+۲+۴+۸+۱۶+... اوکی ؟ اوکی ! خوب به نظرت تا کجا این سری ادامه پیدا میکنه ؟
فکر کنم تا جایی که j به n برسه درست گفتی ! آفرین پس قبول داری حلقه دوم اینجوری تغییر میکنه : ۱و۲و۴و۸و۱۶و...وn
بله قبول دارم ، حالا که قبول داری ، بیا یه فرضی بکنیم ، چه فرضی ؟ بیا فرض کنیم n توانی از دو باشه ، به چه درد میخوره ؟ تو چه کار داری ؟ فقط گوش بده ! باشه گوش میدم ، پس فرض کردیم n=2^k ، قبول ؟ قبول، خوب حالا بیا به این جلمه دقیق تر نگاه کنیم : ۱و۲و۴و۸و۱۶و...وn ، میتونم به جای یک بنویسم دو به توان صفر ؟ بله ، میتونم به جای دو بنویسم دو به توان یک ؟ بله میتونم به جای چهار بنویسم دو به توان دو ؟ بله ، و همینطور الی آخر و آیا میتوانم به جای n بنویسم دو به توان k (بر طبق فرضی که کردیم) ؟ بله میشه نوشت، اگه میشه پس باز نویسی کنم این جوری میشه : ۰^۲ و ۱^۲ و ۲^۲ و .... و تا دو به توان k
به نظرت چند تا عدد هست ؟ نمیدونم ، بترکی اللهی ! خوب توان های دو از چند هستند تا چند ؟ از صفر شروع میشن تا k
آفرین ! خوب پس چند تا عدد داریم ؟ k تا عدد ، بمیری ! k+1 عدد چون از صفر داریم تا k اوکی ؟ اوکی ! خوب بیا از فرضمون الگاریتم بگیریم، حتما الگاریتم رو هم بلد نیستی ! ؟ نه دیگه استاد اینقدر ها بلدم، خوبه ، پس چی میشه ؟ چی چی میشه ؟
اگه از فرضمون الگاریتم بگیریم دیگه ! آهان ، خوب میشه : k=log n ، خوبه پس قبول داری به اندازه log n تا عدد حلقه دوم درست میکنه ؟ بله قبول دارم ، پس باید اینم قبول داشته باشی که حلقه پایینی به اندازه مقدار هر یک از این اعدادی که حلقه دومی میسازه دستور آخر رو اجرا میکنه،قبول ؟ قبول ، خوب پس حلقه سومی داره به اندازه مجموع یه تعداد عدد که همشون هم توان های دو هستند اجرا میشه ، قبول ؟ قبول ، چند تا عدد ؟ الگاریتم n تا عدد ، آهان ، خوبه ، پس قبول داری تعداد اجراهای حلقه سوم اینجوری میشه ؟
۱+۲+۴+۸+۱۶+۳۲+... ؟ بله ! اینو قبلآ هم که گفته بودین بله گفته بودم ولی دو ساعت فک زدم تا بهت حالی کنم تعداد این اعداد لگاریتم n هست. و اگه یکم سواد ریاضی داشته باشی، میفهمی که این سری میشه مجموع اعداد توان دو که چند تا هستن ؟ لگاریتم n ، خوب حالا حاصلش چند میشه استاد ؟ میشه : ۲n-1 چرا ؟ چرا نداره ! چرا رو تو یه داستان دیگه کلی توضیح میدم، همینجوری فعلآ ازم قبول کن ، باشه استاد ، خوب حالا بعد از کلی حرف و توضیح فهمیدیم که دو تا حلقه پایینی به اندازه ۲n-1 اجرا میشه و حالا حلقه اول رو بیار تو کار، چون تعداد تکرار حلقه اول از مرتبه الگاریتم n است و چون این حلقه با این دو تا حلقه کاری نداره (مستقله) باید تعداد اجراهای این حلقه رو در تعداد تکرار دو تا حلقه دیگه ضرب کنیم : یعنی : ۲n-1 * log n
که مرتبش میشه : nlogn

---

چرا رو در ضمیمه آوردم

(۲۱ مهر ۱۳۹۱ ۱۰:۵۲ ب.ظ)m_sardaari نوشته شده توسط:  دوستان اگه کسی میتونه این تست رو تشریح کنه و جوابشو با دلیل بگه ممنون میشم

سلام خوبی

ببین واسه حل این جور حلقه ها باید این کاری که بهت می گم را انجام بدی شما الان ۳ تا حلقه for می بینی for اول را ندید بگیر کلاً برو تو for دوم و سوم

این دو تا به هم وابسته هستند این نکته را یادت باشه که چوت توان ۲ داریم حتماً جواب دو تا حلقه ات logn است حالا باید بری تریس کنی کامل متوجه می شی حلقه ائل هم n بار اجرا می شودپس مرتبه اجرایی می شه گزینه ۳ بازم نفهمیدی بگو

ممنون دوست عزیز.
اگر تعداد اجرای دستور x++ رو بخوایم چی میشه نه مرتبه؟
بعد مگه هر بار i در دو ضرب نمیشه پس کلا حلقه اول n/2 بار اجرا میشه؟!

من توضیحات رو درست متوجه نشدم اگه می شه روشن تر توضیح بدید
این رو میدونم که حتم جواب لوگاریتم
وتوضیحات رو متوجه نشدم

(۲۳ مهر ۱۳۹۱ ۱۲:۰۷ ب.ظ)*Najmeh* نوشته شده توسط:  من توضیحات رو درست متوجه نشدم اگه می شه روشن تر توضیح بدید
این رو میدونم که حتم جواب لوگاریتم
وتوضیحات رو متوجه نشدم

ببین دوست عزیز یک عدد دارای اوگاریتم به حلقه دوم بده رفتارشو را میبینی در واقع i^2 می شه بعد i^4 همینجورب می ره تا به I^k می رسه متوجه شدی