n تا عدد در بازه [tex]\left [ 0, n^{k}-1 \right ][/tex] داریم با چه مرتبه ای می توان این اعداد را مرتب کرد؟
به نظر من اگه توی مبنای n کار کنیم، اعدادمون از ۰ هستن تا [tex]((n-1)(n-1)\dots (n-1))_{n}[/tex] که تعداد ارقام این اعداد k هستش، حال اگه از RadixSort اتسفاده کنیم داریم:
[tex]\theta (d(n p))[/tex] که d میشه تعداد ارقاممون که k هستش، p هم بازه اعدادمون هست که از ۰ هستن تا n-1 که تعدادشون هم میشه n و اگه همه ی اینا رو بزنیم سر هم داریم:
[tex]\theta (k(n (n-1))) = \theta (nk)[/tex]
دوستان اگه نظر دیگه ای هم دارن بگن
چون برا اعداد محدوده مشخص کرده باید از مرتب سازی شمارشی استفاده کنیم که اونم از مرتبه( O (n هستش
(۱۵ مهر ۱۳۹۲ ۰۱:۱۱ ق.ظ)SnowBlind نوشته شده توسط: n تا عدد در بازه [tex]\left [ 0, n^{k}-1 \right ][/tex] داریم با چه مرتبه ای می توان این اعداد را مرتب کرد؟
به نظر من اگه توی مبنای n کار کنیم، اعدادمون از ۰ هستن تا [tex]((n-1)(n-1)\dots (n-1))_{n}[/tex] که تعداد ارقام این اعداد k هستش، حال اگه از RadixSort اتسفاده کنیم داریم:
[tex]\theta (d(n p))[/tex] که d میشه تعداد ارقاممون که k هستش، p هم بازه اعدادمون هست که از ۰ هستن تا n-1 که تعدادشون هم میشه n و اگه همه ی اینا رو بزنیم سر هم داریم:
[tex]\theta (k(n (n-1))) = \theta (nk)[/tex]
دوستان اگه نظر دیگه ای هم دارن بگن
پاسختون درسته به نظرم. البته میشه گفت اگر k ثابت و از مرتیه [tex]o(n)[/tex] باشه ، میتونیم بگیم پاسخ میشه [tex]O(n)[/tex]
(۲۷ آذر ۱۳۹۲ ۰۲:۱۴ ب.ظ)۲۰۱۳محمد نوشته شده توسط: چون برا اعداد محدوده مشخص کرده باید از مرتب سازی شمارشی استفاده کنیم که اونم از مرتبه( O (n هستش
فرمول مرتب سازی شمارشی اینه : [tex]O(n m)[/tex] که m بزرگترین عدد ممکن از بازه هست. در اینجا هم چون بزرگترین عدد [tex]n^{k}[/tex] هست ، بنابراین مرتبه این الگوریتم میشه [tex]O(n n^{k}) = O(n^{k})[/tex] که مسلما ( O (n نمیشه.
الگوریتم شمارشی زمانی از مرتبه ( O (n میشه که m حداکثر برابر n باشه.
این سوال عینا در کتاب طراحی الگوریتم از clrs هست(صفحه ۲۱۰) زمان مرتب سازی هم میشه ( O (n
(۲۸ آذر ۱۳۹۲ ۰۳:۰۲ ق.ظ)۲۰۱۳محمد نوشته شده توسط: این سوال عینا در کتاب طراحی الگوریتم از clrs هست(صفحه ۲۱۰) زمان مرتب سازی هم میشه ( O (n
اونجا توان ۲ هست نه توان k برا همین ۲n میشه با اوردر n