سوال مرتب سازی k لیست(طراحی الگوریتم)
k لیست مرتب داریم و هریک n/k عنصر در خود دارد.در مجموع n عنصر داریم.روش کار:ابتدا لیست اول و دوم را به شکل مرتب ادغام میکنیم سپس لیست حاصل را با لیست سوم و... لیست حاصل با لیست kام ترکیب میشود.در بدترین حالت پیچیدگی زمانی چقدر است؟
۱/ (O(nk
۲/(O(n
۳/(O(nlogk
۴/(O(klogn
نظر من گزینه ۴ البته مطمئن نیستم
منم فکر کنم ۴ باشه ولی نزدم
گیزنه ۱ میشد به خاطر جریمه که میدید میشد
n/k (k(k+1)/2) که میشه همون nk
(۲۸ بهمن ۱۳۹۰ ۰۲:۲۷ ب.ظ)LARACROFT0 نوشته شده توسط: گیزنه ۱ میشد به خاطر جریمه که میدید میشد
n/k (k(k+1)/2) که میشه همون nk
منم همینو زدم
من زدم klogn
وووای من nk زدم بعد پاکش کردم
اون سوال که مرتب سازی نبود. ادغام لیست های مرتب بود که میشه n
منم n زدم
من این سوال رو با کشیدن k لیست به دست آوردم k lg n چون که لیست‌ها مرتب هستند(lg n) و k لیست داریم.
جواب سوال nk بودش، چون هر دفعه کل لیست قبلی رو با بعدی مقایسه میکرد مثلا در بار اول میشه n/k و با n/k مقایسه میکنه یعنی ۲n/k عملیات o(m+n) و دفعه بعد لیست قبلی و با n/k تا عنصر بعدی ترکیب باید کنه که میشه ۳n/k و در کل میشه مجموع اعداد بالا.
که میشه o(nk)
در این قسمت هر یک از دوستان سوال های طراحی الگوریتم رو یادشه ذکر کنه.
بچه‌ها اون سوالی که گفته بود بزرگترین درخت پر رو با چه زمانی می شه بدست بیارید من زدم n شما چی زدین
من nlgn زدم
اگه لیست یک جا بود می شه ON(n) ولی چون گفته بود یکی یکی ادغام می کنیم چون مرتبه می شه O(nk
(۲۸ بهمن ۱۳۹۰ ۰۸:۲۳ ب.ظ)HRZ نوشته شده توسط: من nlgn زدم
دوست عزیز می شه جواب خودتون رو تشریح کنین
دوستان بذارین خیالتونو راحت کنم توی سوالای دانشگاه MIT دقیقا همین سوال مطرح شده اگر ادغام رو با هیپ انجام بدیم O(nlg( می شد ولی اگر به همین روش صورت سوال پیش بریم nk میشه