۰
subtitle
ارسال: #۱
مهندسی نرم افزار - سراسری ۹۱
با عرض سلام
دوستان برای سوال زیر، من می گم اگر k=1 فرض بشه، که مسئله می شه یک آرایه ی مرتب که نیاز به مرتب سازی نداره. پس جواب باید برحسب k به صورت لگاریتمی باشه. (فقط گزینه ی ۳). و اگر هم k=n باشه، مسئله ی Merge Sort مطرح می شه. من خوندم که در الگوریتم Merge Sort تفاوت نمی کنه که آرایه ی اولیه به چه نسبت شکسته بشه، در هر حالت مرتبه ی زمانی [tex]\Theta(n.\log n)[/tex] می شه. پس یعنی اگر طبق گفته ی مسئله حساب کنیم، آرایه ی اولیه به نسبت ۱ و n-1 شکسته می شه، آون آرایه ی n-1 عضوی به نسبت ۱ و n-2 و ... الی آخر تا به n آرایه ی یک عضوی برسیم و با الگوریتم Merge Sort آنها رو ادغام کنیم. پس باز هم گزینه ی ۳ صحیح است. چرا می گه گزینه ی ۲ ؟
با تشکر
دوستان برای سوال زیر، من می گم اگر k=1 فرض بشه، که مسئله می شه یک آرایه ی مرتب که نیاز به مرتب سازی نداره. پس جواب باید برحسب k به صورت لگاریتمی باشه. (فقط گزینه ی ۳). و اگر هم k=n باشه، مسئله ی Merge Sort مطرح می شه. من خوندم که در الگوریتم Merge Sort تفاوت نمی کنه که آرایه ی اولیه به چه نسبت شکسته بشه، در هر حالت مرتبه ی زمانی [tex]\Theta(n.\log n)[/tex] می شه. پس یعنی اگر طبق گفته ی مسئله حساب کنیم، آرایه ی اولیه به نسبت ۱ و n-1 شکسته می شه، آون آرایه ی n-1 عضوی به نسبت ۱ و n-2 و ... الی آخر تا به n آرایه ی یک عضوی برسیم و با الگوریتم Merge Sort آنها رو ادغام کنیم. پس باز هم گزینه ی ۳ صحیح است. چرا می گه گزینه ی ۲ ؟
با تشکر
۰
ارسال: #۲
RE: مهندسی نرم افزار - سراسری ۹۱
سلام
دوست گرامی برای K=1 یکی از بهترین حالت ها اتفاق می افتد ولی در سوال مرتبه بدترین حالت مد نظر است.
و برای k=n حالا به هر صورتی که شکسته شده n تا لیست یک عنصری داریم بحث روی ادغام است در مرتب سازی ادغامی لیست جفت جفت (ممکن است در هر گام یک لیست تنها بماند) با هم ادغام می شوند و بعد حاصل انها هم جفت جفت . ولی در این سوال دو لیست اولیه با هم ادغام و بعد حاصل با لیست اولیه دیگرادغام و دوباره حاصل با لیست اولیه دیگر...
اگر بخواهیم دقیق تر تعدادمقایسه ها رو بدست اوریم در بدترین حالت داریم
در ادغام دو لیست اول [tex]\frac{n}{k}+\frac{n}{k}-1=\frac{2n}{k}-1[/tex] مقایسه
در گام بعدی [tex]\frac{2n}{k}+\frac{n}{k}-1=\frac{3n}{k}-1[/tex] (یک لیست [tex]\frac{n}{k}[/tex]عنصری و [tex]\frac{2n}{k}[/tex])
در گام بعدی [tex]\frac{3n}{k}+\frac{n}{k}-1=\frac{4n}{k}-1[/tex]
.
.
در گام اخر[tex]\frac{(k-1)n}{k}+\frac{n}{k}-1=\frac{kn}{k}-1[/tex]
پس جمع کل مقایسه ها در بدترین حالت برابر با
[tex](\frac{2n}{k}+\frac{3n}{k}+...+\frac{kn}{k})-(k-1)=\frac{n}{k}\: \ast\frac{k(k+1)}{2}-(k-1)=n\: \ast\frac{(k+1)}{2}\: -(k-1)=O(nk)[/tex]
در بهترین حالت هم(با همین ترتیب) در هر ادغام [tex]\frac{n}{k}[/tex] مقایسه انجام می شودو در کل هم [tex](k-1)[/tex] ادغام داریم پس در بهترین حالت تعداد
[tex]\frac{(k-1)n}{k}[/tex] مقایسه نیاز است (اینجا می توانید k=1 بگیرید.)چون [tex]\frac{(k-1)}{k}[/tex] مقداری بین ۰ , ۱ است چه ثابت باشدچه متغیر می توانیم بهترین حالت را از مرتبه[tex]O(n)[/tex] بدانیم
دوست گرامی برای K=1 یکی از بهترین حالت ها اتفاق می افتد ولی در سوال مرتبه بدترین حالت مد نظر است.
و برای k=n حالا به هر صورتی که شکسته شده n تا لیست یک عنصری داریم بحث روی ادغام است در مرتب سازی ادغامی لیست جفت جفت (ممکن است در هر گام یک لیست تنها بماند) با هم ادغام می شوند و بعد حاصل انها هم جفت جفت . ولی در این سوال دو لیست اولیه با هم ادغام و بعد حاصل با لیست اولیه دیگرادغام و دوباره حاصل با لیست اولیه دیگر...
اگر بخواهیم دقیق تر تعدادمقایسه ها رو بدست اوریم در بدترین حالت داریم
در ادغام دو لیست اول [tex]\frac{n}{k}+\frac{n}{k}-1=\frac{2n}{k}-1[/tex] مقایسه
در گام بعدی [tex]\frac{2n}{k}+\frac{n}{k}-1=\frac{3n}{k}-1[/tex] (یک لیست [tex]\frac{n}{k}[/tex]عنصری و [tex]\frac{2n}{k}[/tex])
در گام بعدی [tex]\frac{3n}{k}+\frac{n}{k}-1=\frac{4n}{k}-1[/tex]
.
.
در گام اخر[tex]\frac{(k-1)n}{k}+\frac{n}{k}-1=\frac{kn}{k}-1[/tex]
پس جمع کل مقایسه ها در بدترین حالت برابر با
[tex](\frac{2n}{k}+\frac{3n}{k}+...+\frac{kn}{k})-(k-1)=\frac{n}{k}\: \ast\frac{k(k+1)}{2}-(k-1)=n\: \ast\frac{(k+1)}{2}\: -(k-1)=O(nk)[/tex]
در بهترین حالت هم(با همین ترتیب) در هر ادغام [tex]\frac{n}{k}[/tex] مقایسه انجام می شودو در کل هم [tex](k-1)[/tex] ادغام داریم پس در بهترین حالت تعداد
[tex]\frac{(k-1)n}{k}[/tex] مقایسه نیاز است (اینجا می توانید k=1 بگیرید.)چون [tex]\frac{(k-1)}{k}[/tex] مقداری بین ۰ , ۱ است چه ثابت باشدچه متغیر می توانیم بهترین حالت را از مرتبه[tex]O(n)[/tex] بدانیم
ارسال: #۳
RE: مهندسی نرم افزار - سراسری ۹۱
(۲۷ فروردین ۱۳۹۶ ۱۲:۵۰ ق.ظ)msour44 نوشته شده توسط: سلام
دوست گرامی برای K=1 یکی از بهترین حالت ها اتفاق می افتد ولی در سوال مرتبه بدترین حالت مد نظر است.
و برای k=n حالا به هر صورتی که شکسته شده n تا لیست یک عنصری داریم بحث روی ادغام است در مرتب سازی ادغامی لیست جفت جفت (ممکن است در هر گام یک لیست تنها بماند) با هم ادغام می شوند و بعد حاصل انها هم جفت جفت . ولی در این سوال دو لیست اولیه با هم ادغام و بعد حاصل با لیست اولیه دیگرادغام و دوباره حاصل با لیست اولیه دیگر...
اگر بخواهیم دقیق تر تعدادمقایسه ها رو بدست اوریم در بدترین حالت داریم
در ادغام دو لیست اول [tex]\frac{n}{k}+\frac{n}{k}-1=\frac{2n}{k}-1[/tex] مقایسه
در گام بعدی [tex]\frac{2n}{k}+\frac{n}{k}-1=\frac{3n}{k}-1[/tex] (یک لیست [tex]\frac{n}{k}[/tex]عنصری و [tex]\frac{2n}{k}[/tex])
در گام بعدی [tex]\frac{3n}{k}+\frac{n}{k}-1=\frac{4n}{k}-1[/tex]
.
.
در گام اخر[tex]\frac{(k-1)n}{k}+\frac{n}{k}-1=\frac{kn}{k}-1[/tex]
پس جمع کل مقایسه ها در بدترین حالت برابر با
[tex](\frac{2n}{k}+\frac{3n}{k}+...+\frac{kn}{k})-(k-1)=\frac{n}{k}\: \ast\frac{k(k+1)}{2}-(k-1)=n\: \ast\frac{(k+1)}{2}\: -(k-1)=O(nk)[/tex]
در بهترین حالت هم(با همین ترتیب) در هر ادغام [tex]\frac{n}{k}[/tex] مقایسه انجام می شودو در کل هم [tex](k-1)[/tex] ادغام داریم پس در بهترین حالت تعداد
[tex]\frac{(k-1)n}{k}[/tex] مقایسه نیاز است (اینجا می توانید k=1 بگیرید.)چون [tex]\frac{(k-1)}{k}[/tex] مقداری بین ۰ , ۱ است چه ثابت باشدچه متغیر می توانیم بهترین حالت را از مرتبه[tex]O(n)[/tex] بدانیم
خیلی زحمت کشیدین دوست من، مرسی که وقت می ذارید و کمک می کنید
انشاالله موفق و پیروز باشید
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close