21 مهر 1391, 10:52 ب.ظ
22 مهر 1391, 10:15 ق.ظ
22 مهر 1391, 10:59 ق.ظ
23 مهر 1391, 12:07 ب.ظ
23 مهر 1391, 04:48 ب.ظ
23 مهر 1391, 08:19 ب.ظ
سلام (داستان یک شاگرد شوت و یک استاد با حوصله)
حلقه فور اولی رو بیخیال شو ، پس اول برو سراغ دو تا حلقه فور پاینی، اوکی ؟
خوب چرا این کارو کردیم ؟ چون حلقه اول کاری به دو تا حلقه بعدی نداره یعنی واسه خودش مستقله
مستقل بودن یعنی چی ؟
یعنی این که اندیس حلقه اول که همان i هست داخل حلقه های دیگه وجود نداره 
آقا اجازه ؟
بله بفرما ، پس میشه گفت چون اندیس حلقه دوم توی حلقه سوم هست ( j ) پس حلقه سوم و دوم به هم وابسته هستند ؟ 
بله درست گفتی ! آفرین
حالا بریم ادامه کار ....
قبول داری حلقه دوم اینجوری میشمارد : 1 بعد 2 بعد 4 بعد 8 بعد 16 و الی آخر ؟
بله قبول دارم
حالا که قبول داری،اینم قبول داری که حلقه سوم به اندازه مقدار اندیس حلقه دوم اجرا میشه ؟
نه قبول ندارم ! یعنی نمیفهمم چی میگین !
بترکی ! آی کیو اندازه جلبک دریایی !
باشه یکم آسون تر میگم :
توی حلقه سوم متغییرش چیه ؟ مگه k نیست ؟ بله، خوب مگه از یک شروع نشده ؟ بله ، خوب جونت در بیاد ! مگه تا j پیش نمیره ؟
بله پیش میره ، خوب پس قبول داری حلقه سومی به اندازه j دستور زیرش رو اجرا میکنه ؟
بزار فکر کنم
آهان ! قبول ! ، خوب مگه نگفتی حلقه دوم اینجوری میشمارد : 1 بعد 2 بعد 4 بعد 8 بعد 16 و الی آخر ؟ بله گفتم ، خوب پس حلقه سوم به ازای هر مقداری که j میگیرد دستور زیرش رو اجرا میکنه ، یعنی : وقتی j یک است یکبار اجرا میکنه و وقتی j
دو است دوبار اجرا میکنه و الی آخر ، یعنی : 1+2+4+8+16+... اوکی ؟ اوکی ! خوب به نظرت تا کجا این سری ادامه پیدا میکنه ؟
فکر کنم تا جایی که j به n برسه درست گفتی ! آفرین 
پس قبول داری حلقه دوم اینجوری تغییر میکنه : 1و2و4و8و16و...وn
بله قبول دارم ، حالا که قبول داری ، بیا یه فرضی بکنیم ، چه فرضی ؟ بیا فرض کنیم n توانی از دو باشه ، به چه درد میخوره ؟ تو چه کار داری ؟ فقط گوش بده ! باشه گوش میدم ، پس فرض کردیم n=2^k ، قبول ؟ قبول، خوب حالا بیا به این جلمه دقیق تر نگاه کنیم : 1و2و4و8و16و...وn ، میتونم به جای یک بنویسم دو به توان صفر ؟ بله ، میتونم به جای دو بنویسم دو به توان یک ؟ بله میتونم به جای چهار بنویسم دو به توان دو ؟ بله ، و همینطور الی آخر و آیا میتوانم به جای n بنویسم دو به توان k (بر طبق فرضی که کردیم) ؟ بله میشه نوشت، اگه میشه پس باز نویسی کنم این جوری میشه : 0^2 و 1^2 و 2^2 و .... و تا دو به توان k
به نظرت چند تا عدد هست ؟ نمیدونم ، بترکی اللهی ! خوب توان های دو از چند هستند تا چند ؟ از صفر شروع میشن تا k
آفرین ! خوب پس چند تا عدد داریم ؟ k تا عدد ، بمیری ! k+1 عدد چون از صفر داریم تا k اوکی ؟ اوکی ! خوب بیا از فرضمون الگاریتم بگیریم، حتما الگاریتم رو هم بلد نیستی ! ؟ نه دیگه استاد اینقدر ها بلدم، خوبه ، پس چی میشه ؟ چی چی میشه ؟
اگه از فرضمون الگاریتم بگیریم دیگه ! آهان ، خوب میشه : k=log n ، خوبه پس قبول داری به اندازه log n تا عدد حلقه دوم درست میکنه ؟ بله قبول دارم ، پس باید اینم قبول داشته باشی که حلقه پایینی به اندازه مقدار هر یک از این اعدادی که حلقه دومی میسازه دستور آخر رو اجرا میکنه،قبول ؟ قبول ، خوب پس حلقه سومی داره به اندازه مجموع یه تعداد عدد که همشون هم توان های دو هستند اجرا میشه ، قبول ؟ قبول ، چند تا عدد ؟ الگاریتم n تا عدد ، آهان ، خوبه ، پس قبول داری تعداد اجراهای حلقه سوم اینجوری میشه ؟
1+2+4+8+16+32+... ؟ بله ! اینو قبلآ هم که گفته بودین بله گفته بودم ولی دو ساعت فک زدم تا بهت حالی کنم تعداد این اعداد لگاریتم n هست. و اگه یکم سواد ریاضی داشته باشی، میفهمی که این سری میشه مجموع اعداد توان دو که چند تا هستن ؟ لگاریتم n ، خوب حالا حاصلش چند میشه استاد ؟ میشه : 2n-1 چرا ؟ چرا نداره ! چرا رو تو یه داستان دیگه کلی توضیح میدم، همینجوری فعلآ ازم قبول کن ، باشه استاد ، خوب حالا بعد از کلی حرف و توضیح فهمیدیم که دو تا حلقه پایینی به اندازه 2n-1 اجرا میشه و حالا حلقه اول رو بیار تو کار، چون تعداد تکرار حلقه اول از مرتبه الگاریتم n است و چون این حلقه با این دو تا حلقه کاری نداره (مستقله) باید تعداد اجراهای این حلقه رو در تعداد تکرار دو تا حلقه دیگه ضرب کنیم : یعنی : 2n-1 * log n
که مرتبش میشه : nlogn
چرا رو در ضمیمه آوردم
حلقه فور اولی رو بیخیال شو ، پس اول برو سراغ دو تا حلقه فور پاینی، اوکی ؟
خوب چرا این کارو کردیم ؟ چون حلقه اول کاری به دو تا حلقه بعدی نداره یعنی واسه خودش مستقله
مستقل بودن یعنی چی ؟
یعنی این که اندیس حلقه اول که همان i هست داخل حلقه های دیگه وجود نداره آقا اجازه ؟
بله بفرما ، پس میشه گفت چون اندیس حلقه دوم توی حلقه سوم هست ( j ) پس حلقه سوم و دوم به هم وابسته هستند ؟ بله درست گفتی ! آفرین
حالا بریم ادامه کار ....
قبول داری حلقه دوم اینجوری میشمارد : 1 بعد 2 بعد 4 بعد 8 بعد 16 و الی آخر ؟
بله قبول دارم
حالا که قبول داری،اینم قبول داری که حلقه سوم به اندازه مقدار اندیس حلقه دوم اجرا میشه ؟
نه قبول ندارم ! یعنی نمیفهمم چی میگین !
بترکی ! آی کیو اندازه جلبک دریایی !
باشه یکم آسون تر میگم : توی حلقه سوم متغییرش چیه ؟ مگه k نیست ؟ بله، خوب مگه از یک شروع نشده ؟ بله ، خوب جونت در بیاد ! مگه تا j پیش نمیره ؟
بله پیش میره ، خوب پس قبول داری حلقه سومی به اندازه j دستور زیرش رو اجرا میکنه ؟
بزار فکر کنم
آهان ! قبول ! ، خوب مگه نگفتی حلقه دوم اینجوری میشمارد : 1 بعد 2 بعد 4 بعد 8 بعد 16 و الی آخر ؟ بله گفتم ، خوب پس حلقه سوم به ازای هر مقداری که j میگیرد دستور زیرش رو اجرا میکنه ، یعنی : وقتی j یک است یکبار اجرا میکنه و وقتی jدو است دوبار اجرا میکنه و الی آخر ، یعنی : 1+2+4+8+16+... اوکی ؟ اوکی ! خوب به نظرت تا کجا این سری ادامه پیدا میکنه ؟
فکر کنم تا جایی که j به n برسه
درست گفتی ! آفرین پس قبول داری حلقه دوم اینجوری تغییر میکنه : 1و2و4و8و16و...وnبله قبول دارم ، حالا که قبول داری ، بیا یه فرضی بکنیم ، چه فرضی ؟ بیا فرض کنیم n توانی از دو باشه ، به چه درد میخوره ؟ تو چه کار داری ؟ فقط گوش بده ! باشه گوش میدم ، پس فرض کردیم n=2^k ، قبول ؟ قبول، خوب حالا بیا به این جلمه دقیق تر نگاه کنیم : 1و2و4و8و16و...وn ، میتونم به جای یک بنویسم دو به توان صفر ؟ بله ، میتونم به جای دو بنویسم دو به توان یک ؟ بله میتونم به جای چهار بنویسم دو به توان دو ؟ بله ، و همینطور الی آخر و آیا میتوانم به جای n بنویسم دو به توان k (بر طبق فرضی که کردیم) ؟ بله میشه نوشت، اگه میشه پس باز نویسی کنم این جوری میشه : 0^2 و 1^2 و 2^2 و .... و تا دو به توان k
به نظرت چند تا عدد هست ؟ نمیدونم ، بترکی اللهی ! خوب توان های دو از چند هستند تا چند ؟ از صفر شروع میشن تا k
آفرین ! خوب پس چند تا عدد داریم ؟ k تا عدد
، بمیری ! k+1 عدد چون از صفر داریم تا k اوکی ؟ اوکی ! خوب بیا از فرضمون الگاریتم بگیریم، حتما الگاریتم رو هم بلد نیستی ! ؟ نه دیگه استاد اینقدر ها بلدم، خوبه ، پس چی میشه ؟ چی چی میشه ؟اگه از فرضمون الگاریتم بگیریم دیگه ! آهان ، خوب میشه : k=log n ، خوبه پس قبول داری به اندازه log n تا عدد حلقه دوم درست میکنه ؟ بله قبول دارم ، پس باید اینم قبول داشته باشی که حلقه پایینی به اندازه مقدار هر یک از این اعدادی که حلقه دومی میسازه دستور آخر رو اجرا میکنه،قبول ؟ قبول ، خوب پس حلقه سومی داره به اندازه مجموع یه تعداد عدد که همشون هم توان های دو هستند اجرا میشه ، قبول ؟ قبول ، چند تا عدد ؟ الگاریتم n تا عدد ، آهان ، خوبه ، پس قبول داری تعداد اجراهای حلقه سوم اینجوری میشه ؟
1+2+4+8+16+32+... ؟ بله ! اینو قبلآ هم که گفته بودین
بله گفته بودم ولی دو ساعت فک زدم تا بهت حالی کنم تعداد این اعداد لگاریتم n هست. و اگه یکم سواد ریاضی داشته باشی، میفهمی که این سری میشه مجموع اعداد توان دو که چند تا هستن ؟ لگاریتم n ، خوب حالا حاصلش چند میشه استاد ؟ میشه : 2n-1 چرا ؟ چرا نداره ! چرا رو تو یه داستان دیگه کلی توضیح میدم، همینجوری فعلآ ازم قبول کن ، باشه استاد ، خوب حالا بعد از کلی حرف و توضیح فهمیدیم که دو تا حلقه پایینی به اندازه 2n-1 اجرا میشه و حالا حلقه اول رو بیار تو کار، چون تعداد تکرار حلقه اول از مرتبه الگاریتم n است و چون این حلقه با این دو تا حلقه کاری نداره (مستقله) باید تعداد اجراهای این حلقه رو در تعداد تکرار دو تا حلقه دیگه ضرب کنیم : یعنی : 2n-1 * log nکه مرتبش میشه : nlogn
چرا رو در ضمیمه آوردم