(۱۶ آذر ۱۳۹۲ ۱۰:۰۵ ب.ظ)tarane1992 نوشته شده توسط:  سلام

دوستان جواب گزینه ۴ هست.

میدونم سوال راحتیه برای شما ولی چرا وقتی میگه الگوریتم درجی رو در mergsort استفاده میکنیم پیچیدگی زمانی درجی جواب نمیشه؟؟من علتشو میخواستم بدونم؟


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

سلام
برای اینکه مرتب سازی درجی را برای ۲۰ عنصر اول گفته پس مرتبه مرتب سازی درجی برای این تعداد ، عددی ثابت است که میشود O(1
که تاثیری روی مرتبه کل الگوریتم ندارد. اگر به جای ۲۰ عنصر مقداری بر حسب n میگفت آن وقت تاثیر داشت و باید بررسی میشد.

جوابتون بسیار عالی بود راست میگینا ۲۰ ثابت پس تاثیری نداره.


یک دنیا ممنونم از شما دوست عزیز.

موفق باشید.

سلام
ببخشید من متوجه توضیحات نشدم. چرا ۲۰ تاثیر نداره؟ حالا اگر بیشتر از ۲۰ بود چگونه تاثیر داشت؟
ممنون

(۱۸ آذر ۱۳۹۲ ۰۱:۱۸ ق.ظ)a.hosh نوشته شده توسط:  سلام
ببخشید من متوجه توضیحات نشدم. چرا ۲۰ تاثیر نداره؟ حالا اگر بیشتر از ۲۰ بود چگونه تاثیر داشت؟
ممنون

سلام
پیچیدگی الگوریتم ادغامی nlogn و پیچیدگی درجی از مرتبه n^2 هست. و میدونیم که تعریف پیچیدگی یک مقداری ایده آل گرایانه هست و رفتار دو الگوریتم در بینهایت را مدل می کنه (فرض می کنه که n به سمت بینهایت میل می کنه). در عمل، به طور معمول n برای ما یک عدد ثابت یا محدود هست (در برنامه هامون) و حتی میشه یک الگوریتم نمایی را مثال زد که از یک الگوریتم چند جمله ای هم سریع تر عمل کنه! یعنی ثابتهای این چند جمله ای اونقدر عدد بزرگی باشه که عملاً مقدارش رو از مقدار اون پیچیدگی نمایی هم بیشتر کنه.

در این مورد اگه ما دو الگوریتم رو پیاده سازی کنیم، مثلاً زمان دقیق اجرایی برای ادغامی میشه ۵nlogn+50n+50 و برای درجی ۲n^2+20 (توجه دارید که در بیان پیچیدگی، جملات با درجه پایین حذف می شدن چون بیانگر زمان اجرای عمل اصلی الگوریتم نبودن ولی اینجا از زمان دقیق صحبت می کنیم نه پیچیدگی - همچنین ثابت ها که عموماً مربوط به عواملی چون نوع عملکرد ماشین، زبان برنامه نویسی، نحوه کد نویسی و ... میشن). حالا اگه شما بگیری n=32، ادغامی در ۲۴۵۰ واحد زمانی اجرا میشه و درجی در ۲۰۶۸ واحد زمانی؛ پس میدونی که به ازای n<=32 الگوریتم با پیچیدگی بدترِ شما، زمان اجرایی بهتری داره.

خب حالا میتونی وقتی تکه آرایه های شما تا اندازه ۳۲ کوچیک شد، دیگه شکستن مسأله رو رها کنی و همه این زیر مسأله های کوچیک رو یک تیکه حل کنی و بعد به سلسله ادغام ها بپردازی. در روش عادی که الگوریتم شما تا زیر مسئله هایی به اندازه ۱ پیش میره، تعداد n برگ داریم. چون ۳۲ یا هر عدد دیگه ای ثابت هستش، و به تعداد تقریباً n/32 بار (تعداد برگ ها) اجرا میشه، تغییری در مرتبه نداره و پیچیدگی اجرایی کمتر یا زیادتر نمیشه. در واقع با این کارها ما تعداد ثابتی از سطوح پایینی درخت رو با پرداخت هزینه ای کمتر از اجرای ادغامی روی اونها (حلشون کردیم و) حذف کردیم.

امیدوارم پیچیدگی بالای توضیحاتم intractable نباشه!!!