آرایه ی A تقریبا مرتب شده است یعنی برای i=0,1...n-k داریم A[i+k]=>[A[i برای مرتب نمودن تمام n عضو حداقل چه مقدار لازم است؟
جواب : nlogk
میشه از این نکته استفاده کرد؟
زمان اجرای مرتب سازی سریع را می توان با استفاده از مرتب سازی درجی وقتی ورودی تقریبا مرتب است بهبود بخشید هنگامی که quicksort روی یک آرایه کمتر از K عنصر فراخوانی شد اجازه دهید بدون مرتب سازی زیر آرایه بازگردد پس از آنکه فراخوانی اولیه به quicksort
جواب : nlogk
میشه از این نکته استفاده کرد؟
زمان اجرای مرتب سازی سریع را می توان با استفاده از مرتب سازی درجی وقتی ورودی تقریبا مرتب است بهبود بخشید هنگامی که quicksort روی یک آرایه کمتر از K عنصر فراخوانی شد اجازه دهید بدون مرتب سازی زیر آرایه بازگردد پس از آنکه فراخوانی اولیه به quicksort
O(nk+nlogn/k)[align=left[/align]]
کسی نیست توی این مساله کمک کنه؟
(۱۳ آذر ۱۳۹۱ ۰۳:۴۲ ب.ظ)mahsa.tsi نوشته شده توسط: کسی نیست توی این مساله کمک کنه؟
سلام دوست عزیز
شما میتونید با مقدار دهی k و آزمایش کردن آن مسله را حل کنید
بطور مثال k=1 آنگاه آرایه مرتب است: [tex]a[1]\leq a[2]\leq a[3]\leq ...\leq a[k][/tex]
و نیاز به جابجایی نیست: nlog1=0 و برای k=2 داریم:
[tex]a[1]\leq a[3]\leq a[5] ...[/tex]
و [tex]a[2]\leq a[4]\leq a[6] ...[/tex]
بنابراین از دونیم آرایه مرتب تشکیل شده است که
نیاز به n جابجایی است : [tex]nlog(2)=n[/tex]
و در حالت کلی [tex]k=2^m[/tex] ، آرایه از K زیر
آرایه مرتب تشکیل شده و هر کدام [tex]n/k[/tex]
عنصر دارد که در [tex]m=log(k)[/tex]مرحله که هر
مرحله شامل n جابجایی است کل آرایه را مرتب کرد.
پس آرایه در [tex]nlog(k)[/tex] حل میشود
---------------------------------------
[tex]www.7DataWebDesign.com[/tex]
این نکته تو کتاب CLRS تویه تمرین از فصل ۲ ام کتابش اومده
یه آرایه رو به K زیر آرایه تقسیم می کنیم که طول هر کدوم n/k هست، هر آرایه رو با زمان nk مرتب می کنیم و بعدش کل آرایه ها رو با زمان nlogn/k ام با مرتب سازی درجی مرتبش می کنیم پس میشه nk+nlogn/k ، اگه طول هر زیر آرایه k=logn باشه خواهیم داشت:
با ادغام استاندرد میتونیم آرایه که شامل K زیر لیست رو هر عنصر را در زمان logk (توسط درخت بازنده و برنده) مرتب کنیم پس میتونیم n عنصر را بر فرض مرتب بودن آنها در زمان nlogk مرتب کنیم.
در حقیقت در بدترین حالت دارای nk+nlogn/k هم هست که با مرتب سازی درجی یکسان است اما با توجه به ضرایب کوچیک در مرتب سازی درجی، الگوریتم سریع تر و بهینه تر خواهد شد.
همین مساله تو مرتب سازی سریع هم عینا هست، تو مرتب سازی سریع هم ضرایب بالاست و برای ورودی های کوچک میشه از این روش استفاده کرد که در بدترین حالت میشه مرتب سازی سریع اما در حالت میانگین بهتر و سریع تره .