یه سوال از داشنگاه آزاد بود که نوشته بود بهترین مرتبه زمانی رادیکس میشه o(nlogn) و بدترین میشه O(n2) میخاستم بدونم درسته؟ چطور بهترین میشهnlog n????
(۱۸ بهمن ۱۳۹۲ ۱۲:۲۶ ق.ظ)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)میباشد
پی نوشت:اینا تو کتاب من نوشته
(۱۹ بهمن ۱۳۹۲ ۱۱:۲۸ ق.ظ)izadan11 نوشته شده توسط: طبق گفته ی کتاب clrs ویرایش ۳
"اگر r=lg n انتخاب شود در نتیجه از تتا n خواهد بود"
میشه دلیلشو بگین؟!
