(۱۸ بهمن ۱۳۹۲ ۱۲:۲۶ ق.ظ)g_monireh نوشته شده توسط:  یه سوال از داشنگاه آزاد بود که نوشته بود بهترین مرتبه زمانی رادیکس میشه o(nlogn) و بدترین میشه O(n2) میخاستم بدونم درسته؟ چطور بهترین میشهnlog n????

بدترین حالت زمانی است که n/2 عدد یک رقمی و یک عدد n/2 رقمی وجود داشته باشد که در این صورت n/2+1 عدد داریم که تعداد ارقام آنها حداکثر n/2 است و مرتبه تتا
(n/2(n/2+1+10))
(اعداد مبنای ۱۰)یعنی تتا n^2 است.

جالب اینجاست که بهترین زمان این الگوریتم n است نه nlogn مثلا تعداد ارقام ۳ تا باشه عددم در مبنای ۱۰ یا ۲۰ باشه که بخواهیم با radix
sortش کنیم که اونوقت می شه تتا
(۳(n+20))
یعنی تتا n .

احتمالا nlogn میانگین زمانی این الگوریتم بایستی باشه

موفق باشید....

(۱۸ بهمن ۱۳۹۲ ۱۲:۴۸ ق.ظ)mahsalove نوشته شده توسط:  

(18 بهمن ۱۳۹۲ ۱۲:۲۶ ق.ظ)g_monireh نوشته شده توسط:  یه سوال از داشنگاه آزاد بود که نوشته بود بهترین مرتبه زمانی رادیکس میشه o(nlogn) و بدترین میشه O(n2) میخاستم بدونم درسته؟ چطور بهترین میشهnlog n????

بدترین حالت زمانی است که n/2 عدد یک رقمی و یک عدد n/2 رقمی وجود داشته باشد که در این صورت n/2+1 عدد داریم که تعداد ارقام آنها حداکثر n/2 است و مرتبه تتا
(n/2(n/2+1+10))
(اعداد مبنای ۱۰)یعنی تتا n^2 است.

جالب اینجاست که بهترین زمان این الگوریتم n است نه nlogn مثلا تعداد ارقام ۳ تا باشه عددم در مبنای ۱۰ یا ۲۰ باشه که بخواهیم با radix
sortش کنیم که اونوقت می شه تتا
(۳(n+20))
یعنی تتا n .

احتمالا nlogn میانگین زمانی این الگوریتم بایستی باشه

موفق باشید....

ولی من توی نوتهام نوشتم بهترین از مرتبه ان اوگ ان الانم کتابمو دادم به کسی این تحلیل شماام به نظر درست میرسه پس اینی که من نوشتم چیه؟

در این الگوریتم sتعداد ارقام اعداد وnتعداد اعداد موجود در آرایه میباشد اگر تعداد ارقام اعداد یکسان نبود پشت اعدا کوچکتر صفر را در نظر میگیریم بدیهی است که مرتبه اجرایی آن از مرتبهO(n*s)میباشد که در صورتی که s=nمرتبه ی آن برابر باo(n2)و اگر s=lognاز مرتبهo(nlogn)میباشد

پی نوشت:اینا تو کتاب من نوشته