سلام.
اول :
پیچیدگی الگوریتم چیست؟
مرتبه زمانی چیس؟
ب چه دردی میخورن؟
بعد :
[undefined=undefined]x=0
i=n
while(i>1){
x--
i%=2
}
O(1)
===========
m=n با فرض
for i=1 to n
for j=1 to m
x++;
O(n^2)
=========
for i=0 to n
for j=1 to m
for k=2 to j
x++;
O(n^3)[/undefined]
بگین از کجا میفهمین که مثلا کد بالا O(n^3) میشه؟ چطوری حساب میکنید؟
مرسی
سلام.
کلاً هدف از تحلیل پیچیدگی و مرتبه‌ی زمانی و اینجور چیزا اینه که ببینیم برنامه‌ی ما با تغییر اندازه‌ی ورودی چقدر سرعت اجراش تغییر می‌کنه. مثلاً اگه برناممون می‌تونه برای ورودی با اندازه‌ی صد هزار در عرض ۱ ثانیه اجرا بشه، می‌خوایم پیش‌بینی کنیم که برای ورودی با اندازه‌ی دویست هزار چقدر طول می‌کشه. منظور از اندازه‌ی ورودی می‌تونه تعداد ورودی باشه (مثلاً تعداد اعضای آرای برای الگوریتم مرتب‌سازی) یا این که خود مقدار یک ورودی (مثلاً مقدار n در الگوریتم محاسبه‌ی n فاکتوریل).
این تحلیل‌ها به این درد میخورن که ما یه معیاری برای بهتر کردن کارایی الگوریتم‌هامون داشته باشیم و معمولاً فقط زمانی مفید هستند که اندازه‌ی ورودی‌ها بزرگه و زمان اجرا اهمیت پیدا می‌کنه. مثلاً برای مرتب‌کردن کد ملی همه ایرانی‌ها (ورودی با اندازه‌ی ۷۰ میلیون) اگه ما بدونیم یه الگوریتمی مثل Bubble Sort مرتبه‌ی زمانیش چقدره، می‌تونیم بدون این که امتحان کنیم پیش‌بینی کنیم که اجراش ساعت‌ها و روزها ممکنه طول بکشه، در نتیجه از همون اول دنبال یه الگوریتم مناسب‌تر (با مرتبه‌ی زمانی کم‌تر) می‌گردیم که در عرض کم‌تر از یک ثانیه برامون این مرتب‌سازی رو انجام بده.
طبق توضیحات بالا میشه نتیجه گرفت که برای ورودی‌های با اندازه‌ی کم برامون اهمیت زیادی نداره که مرتبه‌ی الگوریتم چقدره، چون همه الگوریتم‌ها خیلی سریع کار می‌کنند و اصلاً ممکنه تفاوتشونم متوجه نشیم. برای همینم وقتی پیچیدگی رو حساب می‌کنیم همیشه برای ورودی‌های خیلی بزرگ محاسبه می‌کنیم و اندازه‌ی ورودی رو بی‌نهایت در نظر می‌گیریم.
البته موقع استفاده عملی از الگوریتم‌های مختلف خیلی فاکتورها در نظر گرفته میشه، ولی در کل این پیچیدگی زمانی (مرتبه‌ی زمانی) یکی از مهم‌ترین فاکتورها در انتخاب یک الگوریتم از بین چند الگوریتمی هستش که همشون یک کار رو برامون انجام می‌دهند.
جواب بعد:
برای اولی، شما هر nای بدین (به عبارت دیگه: اندازه‌ی ورودی هر چقدر که باشه)، حلقه‌ی while تنها و تنها یک بار اجرا میشه، چون همون بار اول مقدار i یا صفر میشه یا یک و دیگه شرط حلقه برقرار نخواهد بود و از حلقه میاد بیرون. بنابراین چون زمان اجرای این کد به مقدار ورودی بستگی نداره پس مرتبه‌ی زمانیش O(1) هستش.
برای دومی، اگه ما مقدار n رو مثلاً دو برابر کنیم، هم حلقه‌ی اول و هم حلقه‌ی دوم دو برابر بیشتر اجرا می‌شوند. چون این دو حلقه داخل هم هستند، بنابراین کل دفعات اجرای کد داخل حلقه‌ها (یعنی x++) چهار برابر میشه و کل زمان اجرای کد ۴ برابر میشه. اگه مقدار n سه برابر بشه، هر دو حلقه اجراشون ۳ برابر میشه و در نتیجه زمان اجرای کل کد ۹ برابر میشه. میبینیم که با k برابر شدن مقدار nمون، زمان اجرای کدمون داره k^2 برابر میشه. پس کل کد مرتبه‌ی زمانیش میشه O(n^2).
برای کد سومی:
حلقه‌ی سوم که به مقدار j بستگی داره، برای j = 1 اصلاً اجرا نمیشه. برای j=2 تنها یک بار اجرا میشه. برای j = 3 تنها دو بار اجرا میشه و به همین ترتیب برای j = r به تعداد r-1 بار اجرا میشه. بنابراین کد داخل حلقه‌ی سوم (x++) به همین تعداد دفعات اجرا میشه. یعنی برای j=1 هیچی، برای j=2 یک بار و... . در نتیجه بدون در نظر گرفتن حلقه‌ی اول، کد داخل حلقه‌ی سوم ۰ + ۱ + ۲ + ... + m-1 بار اجرا میشه که برابره با ۲ / (m-1) * m دفعه. کل حلقه‌ی دوم و سوم هم با همدیگه داخل حلقه‌ی اول هستند و n بار اجرا میشن. یعنی کل دفعات اجرای کد داخل حلقه برابر ۲ / (m-1) * m * n هستش.
حالا اگه اندازه‌ی ورودی دو برابر بشه (یعنی n = m دو برابر بشن)، در این صورت تعداد کل دفعات اجرای کد داخل حلقه‌ها ۲ / (۲m-1) * 2m * 2n میشه که تقریباً برابره با ۸ * (۲ / (m-1) * m * n) یعنی ۸ برابر دفعات اجرای کد با اندازه‌ی n. پس زمان اجرای کل کدمون ۸ برابر میشه. میبینیم که با تغییر اندازه‌ی ورودیمون به k برابر، کل زمان اجرای کدمون حدوداً k^3 برابر میشه. پس مرتبه‌ی زمانی کدمون O(n^3( هستش.
سعی کردم یک کم شهودی‌تر بگم، ولی بازم ریاضیات قاطیش شد. امیدوارم خوب گفته باشم، ولی اگه بازم سؤالی بود در خدمتم :-)
سلام دوست عزیز ، خیلی خوب گفتین
فقط اون تقسیم به ۲ ها حکمتش چیه ؟
همچنین منم یک سوال دارم :
من ۲ تست همراه راه حلش رو قرار میدم ، میخواستم در مورد تفاوتشون و همچنین قضیه مستر سوال بپرسم .
اولا قضیه مستر چی هست ؟
ثانیا آیا همیشه وقتی یک حمله در خودش ضرب شده بود ما هنگام نوشتن تابع زمانی باید ضربدر ۲ کنیمش ، اما وقتی جمع شده بود باید علاوه بر ضربدر ۲ ، به اضافه ۱ هم بکنیمش؟
امیدوارم خوب تونسته باشم بپرسم .
این تست ها و پاسخ هاشون :
[attachment=12777]
[attachment=12776]
[attachment=12775]
(۱۵ شهریور ۱۳۹۲ ۰۲:۳۵ ب.ظ)mohandess نوشته شده توسط: سلام دوست عزیز ، خیلی خوب گفتین
فقط اون تقسیم به ۲ ها حکمتش چیه ؟
همچنین منم یک سوال دارم :
من ۲ تست همراه راه حلش رو قرار میدم ، میخواستم در مورد تفاوتشون و همچنین قضیه مستر سوال بپرسم .
اولا قضیه مستر چی هست ؟
ثانیا آیا همیشه وقتی یک حمله در خودش ضرب شده بود ما هنگام نوشتن تابع زمانی باید ضربدر ۲ کنیمش ، اما وقتی جمع شده بود باید علاوه بر ضربدر ۲ ، به اضافه ۱ هم بکنیمش؟
امیدوارم خوب تونسته باشم بپرسم .
این تست ها و پاسخ هاشون :
سلام.
در مورد تقسیم به ۲ در پاسخ قبلی:
حاصل جمع [tex]0 1 2 3 ... (m-1)[/tex] برابر میشه با: [tex]\frac{m\times(m-1)}{2}[/tex] و این ۲ از همینجا میاد ;-)
در مورد سؤال جدیدتون:
اون ۱ که اضافه میشه، اون ۱ در واقع نشان‌دهنده‌ی یک عدد ثابت c هست که علاوه بر هزینه‌ی عملیات بازگشتی باید در نظر گرفته بشه و بنابراین برای محاسبه‌ی زمان اجرا همیشه (چه ضرب چه جمع) اون ۱+ باید در نظر گرفته بشه. چون توی ضرب نقشی در نتیجه‌ی محاسبه نداره بعضی از افراد اشتباهاً نمیذارنش ;-).
به نظرم الان یک کم زود به سراغ تست رفتین و شاید بهتر باشه اول خود مطلب رو کمی عمیق‌تر یاد بگیرین :-)
بازم اگه سؤالی بود در خدمتم :-)
اگه [tex]T(n)[/tex] زمان اجرای برنامه برای [tex]n[/tex] تا عدد باشه، [tex]T(\frac {n}{2})[/tex] میشه زمان اجرا واسه [tex]\frac {n}{2}[/tex] تا عدد و همچنین [tex]T(n-1)[/tex] میشه زمان اجرا واسه [tex]n-1[/tex] عدد و الی آخر....
حالا واسه سوال اول اومده توی تابع [tex]test(n)[/tex] دوبار تابع test رو صدا زده، یعنی حل مسئله با سایز n رو اومده تبدیل کرده به ۲ تا مسئله یکی با سایز n-1 و دیگری با سایز n-2. حالا [tex]T(n)[/tex] زمان اجرای تابع ما برای n تا ورودی میشه زمان اجرا برای n-1 تا ورودی به علاوه زمان اجرا برای n - 2 تا ورودی به علاوه یه دونه ضرب. حالا اگه ما [tex]T(n)[/tex] رو بخواهی بر اساس زیر مسئله حا نشون بدیم میشه:
[tex]T(n) = T(n-2) T(n-2) 1[/tex] که اون ۱ هم میشه هزینه ضرب حالا این رابطه بازگشتی رو با روش تکرار حل کنید فرم کلی [tex]T(n)[/tex] بدست میاد.
توی بعضی از این مسائل رابطه [tex]T(n) = aT(\frac {n}{b}) f(n)[/tex] میشه که این نوع رابطه رو میشه بدون حل و با قضیه اصلی حل کرد.
ممنون دوستان
متاسفانه من به خاطر ذیق وقت (درست نوشتم ؟ ) دارم از رو پوران میخونم ، اونم کتاب مشترک الگوریتم و ساختمان ... اونجا خیلی خلاصه و تیتر وار گفته و من سعی میکنم نکات اضافی رو توی حل تست ها یاد بگیرم . مثلا همون +۱ واسم سوال شده بود که چرا یکجا گذاشته یکجا نگذاشته که با راهنمایی شما رفتم یه نگاهی تو clrs انداختم و منوجه شدم .
نمیدونم روشم درسته یا غلط اما از ترس زمان ، فعلا از رو همین پوران میرم جلو و تست میزنم و بازم اگر جایی گیر کردم سعی میکنم تو کتاب پیدا کنم و یا اینجا از دوستان بپرسم . امیدوارم روشم جواب بده!!
(۱۵ شهریور ۱۳۹۲ ۰۹:۲۳ ب.ظ)mohandess نوشته شده توسط: ممنون دوستان
متاسفانه من به خاطر ذیق وقت (درست نوشتم ؟ ) دارم از رو پوران میخونم ، اونم کتاب مشترک الگوریتم و ساختمان ... اونجا خیلی خلاصه و تیتر وار گفته و من سعی میکنم نکات اضافی رو توی حل تست ها یاد بگیرم . مثلا همون +۱ واسم سوال شده بود که چرا یکجا گذاشته یکجا نگذاشته که با راهنمایی شما رفتم یه نگاهی تو clrs انداختم و منوجه شدم .
نمیدونم روشم درسته یا غلط اما از ترس زمان ، فعلا از رو همین پوران میرم جلو و تست میزنم و بازم اگر جایی گیر کردم سعی میکنم تو کتاب پیدا کنم و یا اینجا از دوستان بپرسم . امیدوارم روشم جواب بده!!
حالا شاید دوستان نظر دیگه‌ای داشته باشن، ولی تجربه‌ی شخصیم میگه که اگه حتی ۳-۴تا درس رو کامل و عمیق بخونین نتیجه‌ای که می‌گیرین خیلی بهتر از موقعی هستش که همه رو فقط خونده باشین. علتش هم اینه که سؤالات تقریباً مفهومی هستند و زیاد مثل کنکور سراسری نیستند که نکته تستی و اینا داشته باشن.
البته به هر روشی که می‌خونین امیدوارم خیلی موفق باشید :-)
این اسلایدا رو ببین، شاید به کار بیاد.