(۰۴ بهمن ۱۳۹۴ ۱۰:۳۷ ب.ظ)LEA3C نوشته شده توسط:  جواب رو در پیوست گذاشتم
اگر توضیح بیشتر لازم بود بفرمایید تا خدمتتون عرض کنم

(۰۴ بهمن ۱۳۹۴ ۱۰:۵۵ ب.ظ)Black.Star نوشته شده توسط:  سلام
سوال خوبیه، اگه قبلا با این نوع سری‌ها آشنا باشین که می‌تونین به صورت شهودی جواب رو که یه سری هارمونیکه رو بدین، اما اگه نباشین هم مهم نیست، چون با یک Trace ساده میشه جواب رو پیدا کرد. یه عدد توان ۲ رو برای N مثال می‌زنیم و می‌بینیم تو هر بار اجرای کامل دو حلقه چه مقادیری به دست میاد:

STEP-1: N=8 | I=1 | J=1,2,3,4,5,6,7,8 | TOTAL=8 = Upper Limit 8/1

خب با مقدار اولیه N=8 چند بار اجرا شد؟ ۸ بار، چون مقدار I=1 بود و پرشی نداشتیم. حالا پس از اتمام گام اول اتفاقی که افتاده اینه که I یکی به مقدارش اضافه شده طبق گام حرکتی حلقه For خط اول شبه کد، پس اتفاقی که تو دور دوم میفته اینه که J ما بجای یکی یکی جلو رفتن باید دو تا دو تا جلو بره، ببینیم:

STEP-2: N=8 | I=2 | J=1,3,5,7 | TOTAL=4 = Upper Limit 8/2

خب، تعداد تکرار حلقه دوم به نصف کاهش پیدا کرد. بریم تا آخر ببینیم چی میشه و بعدش نتیجه گیری کنیم:

STEP-3: N=8 | I=3 | J=1,4,7 | TOTAL=3 = Upper Limit 8/3
STEP-4: N=8 | I=4 | J=1,5 | TOTAL=2 = Upper Limit 8/4
STEP-5: N=8 | I=5 | J=1,6 | TOTAL=2 = Upper Limit 8/5
STEP-6: N=8 | I=6 | J=1,7 | TOTAL=2 = Upper Limit 8/6
STEP-7: N=8 | I=7 | J=1,8 | TOTAL=2 = Upper Limit 8/7
STEP-8: N=8 | I=8 | J=1 | TOTAL=1 = Upper Limit 8/8

خب می‌بینیم که بار اول N بار بار دوم N/2 و... بار آخر هم N/N بار اجرا شد، یعنی به صورت کلی تعداد کل اجراهای به صورت زیر میشه، فقط اینکه ما باید برای Trace دستی خودمون یه رابطه پیدا کنیم، وقتی بار اول ۸ بار بار دوم ۳ و ۲ و ۲ و... بار اجرا شد، به این نتیجه می‌رسیم که حد بالا - Upper Limit - متغیر N در هر مرحله تقسیم بر I میشه و ما می‌تونیم رابطه زیر رو به دست بیاریم. البته توی پرانتز بگم که در محاسبه سری حد بالا و پایین رو نادیده می‌گیریم اما برای محاسبه خودمون لازم بود که بدونیم.

من هرچی دارم سعی می‌کنم با این ابزار فرمول نویسی نمیشه چیزی نوشت، همش قاطی میشه، ولی نتیجه گیری اینه که ما یه سیگما از I=1 تا N داریم که تا رسیدن به N هر بار عمل تقسیم N/I رو انجام میده، خب این یعنی میشه با استفاده از حدگیری و قاعده هوپیتال و... اثبات کرد چنین سری‌ای برای حلقه J به نتیجه تتا Logn ختم میشه و یک n هم که از حلقه I داشتیم که نهایتا داریم: تتا nLogn .