با عرض سلام
دوستان لطف می کنید سوال زیر رو راهنمایی بفرمایید لطفا؟
با تشکر
سلام و وقت بخیر ... برای مرتب سازی آرایه ها ( به صورت مجزا ) ابتدا باید بدانیم که در هر آرایه چه تعداد عنصر قرار گرفته است ، در حالت میانگین در هر آرایه حدود [tex]\frac{k}{n}[/tex] عنصر وجود دارد و در بدترین حالت تقریبا همه عناصر در یک آرایه قرار دارد که اندازه آن آرایه تقریبا همان [tex]k[/tex] است .
هزینه مرتب سازی در حالت میانگین برای همه آرایه ها برابر با [tex]n(\frac{k}{n}\log\frac{k}{n})=O(klog\frac{k}{n})[/tex] خواهد بود و در بدترین حالت ( که توضیح دادم ) برابر با [tex]O(klogk)[/tex] خواهد بود ( گزینه چهارم ) که انگار طراح به همین نکته اشاره داشته است .
(۲۳ فروردین ۱۳۹۶ ۰۳:۰۶ ب.ظ)alireza01 نوشته شده توسط: سلام و وقت بخیر ... برای مرتب سازی آرایه ها ( به صورت مجزا ) ابتدا باید بدانیم که در هر آرایه چه تعداد عنصر قرار گرفته است ، در حالت میانگین در هر آرایه حدود [tex]\frac{k}{n}[/tex] عنصر وجود دارد و در بدترین حالت همه عناصر در یک آرایه قرار دارد که اندازه آن آرایه همان [tex]k[/tex] است .
هزینه مرتب سازی در حالت میانگین برای همه آرایه ها برابر با [tex]n(\frac{k}{n}\log\frac{k}{n})=O(klog\frac{k}{n})[/tex] خواهد بود و در بدترین حالت ( که توضیح دادم ) برابر با [tex]O(klogk)[/tex] خواهد بود ( گزینه چهارم ) که انگار طراح به همین نکته اشاره داشته است .
سلام دوست عزیز
مگه نگفته که تعداد عناصر آرایه یه عدد صحیح بین ۱ تا K هست ؟ پس در بدترین حالت، یک عنصر در n-1 آرایه قرار داره و k-n+1 عنصر در یک آرایه. درست نمی گم ؟
(۲۳ فروردین ۱۳۹۶ ۰۳:۲۱ ب.ظ)alimamala نوشته شده توسط: سلام دوست عزیز
مگه نگفته که تعداد عناصر آرایه یه عدد صحیح بین ۱ تا K هست ؟ پس در بدترین حالت، یک عنصر در n-1 آرایه قرار داره و k-n+1 عنصر در یک آرایه. درست نمی گم ؟
سلام .
در این سوال نکته ای که بر مرتب سازی یک آرایه باید به آن اشاره کرد ( چون خاصیت خاصی برای آرایه در نظر نگرفته ) باید طول آرایه را هندلینگ کنیم هر چقدر طول آرایه بیشتر باشه طبیعی است که هزینه مرتب سازی زیاد تر میشه . خوب بدترین حالت زمانی است که [tex]n-1[/tex] ارایه کمترین طول را داشه باشند ( یعنی یک عنصر ) و باقی مانده عناصر یعنی [tex]k\: -\: ((n-1)\ast1)=k-(n-1)[/tex] داشته باشه . برای محاسبه هزینه مرتب سازی این آرایه کافی است بدانیم که در این حالت [tex]k-n+1\: \ge\: 1\: \Longrightarrow\: k\ge\: n[/tex] پس هزینه مرتب سازی [tex]O((k-n+1)\log(k-n+1))=O((k-n+1)(\log k+\log(1+\frac{n-1}{k})))=O(klogk)[/tex] که همان مرتبه ای بود که عرض کردم .