۱
subtitle
ارسال: #۱
حل سوال ۵۰ کنکور ۹۲ (مهندسی)- مرتبه مرتب سازی یک بازه عددی
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]
دوستان اگه نظر دیگه ای هم دارن بگن
به نظر من اگه توی مبنای 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]
دوستان اگه نظر دیگه ای هم دارن بگن
Masoud05، در تاریخ ۲۹ آذر ۱۳۹۲ ۱۱:۰۵ ب.ظ برای این مطلب یک پانوشت گذاشته است:
خواهشا عنوان تاپیک رو درست انتخاب کنید ، این مورد رو خودم اصلاح کردم ، انشاالله در اینده توجه کافی رو داشته باشید
۰
ارسال: #۲
RE: حل سوال ۵۰ کنکور ۹۲ (مهندسی)
چون برا اعداد محدوده مشخص کرده باید از مرتب سازی شمارشی استفاده کنیم که اونم از مرتبه( O (n هستش
۰
ارسال: #۳
RE: حل سوال ۵۰ کنکور ۹۲ (مهندسی)
(۱۵ مهر ۱۳۹۲ ۰۱:۱۱ ق.ظ)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 باشه.
۰
ارسال: #۴
RE: حل سوال ۵۰ کنکور ۹۲ (مهندسی)
این سوال عینا در کتاب طراحی الگوریتم از clrs هست(صفحه ۲۱۰) زمان مرتب سازی هم میشه ( O (n
ارسال: #۵
RE: حل سوال ۵۰ کنکور ۹۲ (مهندسی)
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close