این سوا در مورد پیچیدگی بهترین الگوریم برای الگوریم داده شذه است که میشه ثابت کرد قطعا از درجه nlogk
است اما انچه که یاعث شبهناک بودنه گزینه ۱ و ۳ هست
حالت متوسط nlogk
یا همیشه از درجه nlogk است در مفهوم چه فرقی دارند
اقای مقسمی گزینه ۱ را زدند
اقای قلی زاده گزینه ۳ را زدند.
!!
با سلام
اول از لحاظ مفهمی:
وقتی میگه حالت متوسط یعنی میتونه مرتبه یا هزینه ما بیشتر از این مقدار هم بشه اما وقتی میگه همیشه یعنی چه در در حالت بدترین و چه در حالت متوسط یا بهترین همیشه همین مقدار را باید هزینه کنیم.
و اما در ادامه ...
بگذارید اینجور توضیح بدم که فرض کنید این همان الگرویتم مرتب سازی سریع است .
توضیح: در مرتب سازی سریع ما تا زمانی که به ارایه های تک عضوی برسیم مراحل تقسیم و پارتیشن بندی را انجام میدهیم .
حال اینطور تصور کنید که این الگوریتم وقتی به ارایه هایی به طول [tex]\frac{N}{K}[/tex]
رسید دیگر پارتیشن بندی را متوقف کرده و کار تمام شده است .
محاسبه پیچدگی:
در این الگروریتم هر بار هزینه پارتیشن بندی را داریم [tex]O(n)[/tex]
اما عمق درخت از Lgn به Lgk کاهش پیدا میکند زیرا:
تعداد گره‌ها در برگها برابر با [tex]\frac{N}{K}[/tex] میباشد .(در مرتب سازی سریع تا ۱ پیش میرفتیم )و لذا داریم: :
[tex]\frac{N}{2^{h}}= \frac{N}{K} \Rightarrow h=log(k)[/tex]
و در نهایت همیشه مرتبه ان برابر است با ::[tex]Nlog(k)[/tex]
نکته اخر بر سر اختلاف نظر بزرگان در حل این تست:
همانطور که میدانید کارایی مرتب سازی سریع به نحوه پارتیشن بندی بستگی دارد اگر پارتیشن بندی به طرز مناسبی صورت گیرد لذا مرتب سازی سریع همیشه nlgn است و همانطور که میدانید در بدترین حال از مرتبه ۲ است اما الگوریتمهایی وجود دارندکه با انتخاب عنصر محور مناسب جهت پارتیشن بندی (روش میانه سه و یا انتخاب تصادفی) همواره هزینه nlgn را دارند و لذا هزینه ان همیشه nlgn است (برای اثبات قضیه به کتاب Clrs مراجعه کنید.)
تمام ماجرا همین بود
موفق باشید.
خوب پس بزارید ببینیم من درست متوجه شدم یا نه:
درسته الگوریتم سریع در بدتریت حات درجهn^2 را داره اما باید دید طراح احتمال وقوع بدترین ورودی را در نظر داشته است با خیر اگر فرض طراح randomized _quick sort (یا هر الگوریتم انتخاب تصادفی میانه) باشد
باید گفت بدترین حالت چون رخ نمیدهد (یا با احتمال خیلی کم )پس همیشه از درجه nlog n میباشد
و در این سوال گزینه همیشه از درجه nlog k _با همون در نظر داشتن فرض بالا _انتخاب میشه.
جواب این سوال گزینه ۱ میشه حالا چرا؟
nعنصر داریم که میخواهیم آنها رابهkمجموعه پارتیشن کنیم که همه عناصر مجموعه اول از همه عناصر مجموعه دوم،همه عناصرمجموعه دوم از همه عناصر مجموعه سوم و...کوچکترهستند.برای اینکار ابتدا میانه راپیداکرده که هزینه آنO(n وروی آنpivot میزنیم دراینصورت همه عناصر سمت چپ ازآن کوچکتر وهمه عناصرسمت راست ازآن بزرگترهستند(درواقع انکاردوتا مجموعه ساختیم)سپس دوباره همین اعمال را روی زیر آرایه‌ها انجام میدیمیعنی میانه هرزیر آرایه رابدست میاوریم وتا آخر...وقتی kتا مجموعه داریم باید log k بار آرایه رابشکنیم وچون هزینه هر سطرO(n پس در مجموع همیشه از مرتبهnlogkهست.امیدوارم متوجه شده باشید.
(۳۰ دى ۱۳۹۰ ۰۲:۴۹ ب.ظ)fatima1537 نوشته شده توسط:چون ما آرایه nرابه۲تاn/2شکستیم هزینه پیداکردن میانه هرn/2ما همون O(n هست.(30 دى ۱۳۹۰ ۰۱:۴۰ ب.ظ)matina نوشته شده توسط: وچون هزینه هر سطرO(n پس در مجموع همیشه از مرتبهnlogkهست.منظور از هر سطر چیه؟ همون هزینه پیدا کردن میانه است؟
دوست متین من متوجه شده بودم و اصلش اینه که جواب را بدست اورده بودم اما نمی فهمیدم که همیشه از درجه nlogk با به طور متوسط از درجه nlog k چه فرقی دارند که با توضیحات دوستان اونم برطرف شد و به گزیه همیشه از درجه nlogk روی اوردم!