۱
subtitle
ارسال: #۱
حل سوال ۵۰ کنکور ۹۲ (مهندسی)- مرتبه مرتب سازی یک بازه عددی
n تا عدد در بازه [0,nk−1] داریم با چه مرتبه ای می توان این اعداد را مرتب کرد؟
به نظر من اگه توی مبنای n کار کنیم، اعدادمون از ۰ هستن تا ((n−1)(n−1)…(n−1))n که تعداد ارقام این اعداد k هستش، حال اگه از RadixSort اتسفاده کنیم داریم:
θ(d(np)) که d میشه تعداد ارقاممون که k هستش، p هم بازه اعدادمون هست که از ۰ هستن تا n-1 که تعدادشون هم میشه n و اگه همه ی اینا رو بزنیم سر هم داریم:
θ(k(n(n−1)))=θ(nk)
دوستان اگه نظر دیگه ای هم دارن بگن
به نظر من اگه توی مبنای n کار کنیم، اعدادمون از ۰ هستن تا ((n−1)(n−1)…(n−1))n که تعداد ارقام این اعداد k هستش، حال اگه از RadixSort اتسفاده کنیم داریم:
θ(d(np)) که d میشه تعداد ارقاممون که k هستش، p هم بازه اعدادمون هست که از ۰ هستن تا n-1 که تعدادشون هم میشه n و اگه همه ی اینا رو بزنیم سر هم داریم:
θ(k(n(n−1)))=θ(nk)
دوستان اگه نظر دیگه ای هم دارن بگن
Masoud05، در تاریخ ۲۹ آذر ۱۳۹۲ ۱۱:۰۵ ب.ظ برای این مطلب یک پانوشت گذاشته است:
خواهشا عنوان تاپیک رو درست انتخاب کنید ، این مورد رو خودم اصلاح کردم ، انشاالله در اینده توجه کافی رو داشته باشید
