جواب سوال اولی که radix sort هست به نظر من میشه گزینه ۲ . یعنی پارسه گزینه ۲ زده
شما فرض کن مبنا مساوی ۱۰ هستش پس میتونیم نتیجه بگیریم که اعداد از ۰ تا n-1 هستن دیگه
۰-۱-۲-۳-۴-۵-۶-۷-۸-۹ ( چرا ؟ چون بیشتر از ۱۰ که دیگه مبنا ده دهی نمیشه )
درست ؟
حالا این گفته ۰ تا n^2-1 یعنی ۲ بار مرتب سازی رو اعمال کرده که هر بار بازه اعداد ۰ تا n-1 بوده
حالا تو هر بار مرتب سازی متوسط زمان اجرا میشه (O(n . پس کل زمان اجرا میشه ( ۲ بار radix )
(O(n+n که میشه (O(n

(۲۴ دى ۱۳۹۳ ۰۱:۰۴ ب.ظ)ardaaalan نوشته شده توسط:  جواب سوال اولی که radix sort هست به نظر من میشه گزینه ۲ . یعنی پارسه گزینه ۲ زده
شما فرض کن مبنا مساوی ۱۰ هستش پس میتونیم نتیجه بگیریم که اعداد از ۰ تا n-1 هستن دیگه
۰-۱-۲-۳-۴-۵-۶-۷-۸-۹ ( چرا ؟ چون بیشتر از ۱۰ که دیگه مبنا ده دهی نمیشه )
درست ؟
حالا این گفته ۰ تا n^2-1 یعنی ۲ بار مرتب سازی رو اعمال کرده که هر بار بازه اعداد ۰ تا n-1 بوده
حالا تو هر بار مرتب سازی متوسط زمان اجرا میشه (O(n . پس کل زمان اجرا میشه ( ۲ بار radix )
(O(n+n که میشه (O(n

بله جواب ۲ است اشتباه تایپی من است که ۴ زدم ولی منظورم همین بود که ۲ جواب نمیشه مگر الگوریتم به تعداد ارقام عدد تکرار نمیشه؟؟خب وقتی اعداد در بازه ۰ تا n2-1 است بالاخره تعداد ارقام مشخص نیست مثلا اگر n=1000 باشد تعداد ارقام آن ۰تا ۷ است ؟

در مورد قسمت اول سوالتون که مییگین باید بگم که تو الگوریتم radix sort ما اصلاً بازه ای از ۰ تا n^2-1 نداریم . این نشون میده که مرتب سازی radix sort 2 بار روی الگوریتم تکرار شده . چون تو هر بار radix مرتب سازی روی آرایه های ۰ تا n-1 آنجام میگیره و اینکه تو radix sort بله به تعداد ارقام عدد مرتب سازی تکرار میشه .
بهتره اینطوری بگم
تو radix زمان اجرامون برابر با چیه ؟؟ (O(n+r
خوب
حالا اینجا n آرایمونه که از فاصله ۰ تا n-1 هستش
حالا r هم پایمونه . پایمونم برابر n هستش . خوب تو زمان اجرای بالا بزاری ۱ بار مرتب سازی زمان (O(n صرف میکنه
۲ بار مرتب سازی انجام شده . ۲ بار (O(n که میشه (O(n+n
حالا بازم تحلیل من و اون چیزی که خوندم اینو میگه . نمیدونم در چه حد درست یا غلط باشه