کم رشدترین حد بالای زمان اجرای الگوریتم مرتب سازی n عدد صحیح در بازه ۰ تا ۲^n در بدترین کدام است
جواب این سوال از مرتبه n اعلام شده
سوالی نزدیک با همین سوال در کنکور it 88 با این مضمون امده که
الگوریتم radix sort را روی n عدد در فاصله (۱-۲^n و ۰) اجرا می کنیم پایه استفاده شده برابر n است متوسط زمان اجرای الگوربتم چقدر است؟
می داتم که چون مبنا n است پس تعداد ارقام هر عدد ۲ است(لگاریتم ۲^n در مبنای n) و در نتیحه جواب برابر است با ۲*(n+n) یعنی از مرتبه n
در مورد سوال اول در یک حل المسایل گفته بود الگوریتم را radix sort در نظر می گیریم و به جواب n می رسبم ولی به نظر من چون اعداد صحیح هستند پس مبنای اعداد ۱۰ است بنابراین تعداد ارقام هر عدد برابر است با لگاریتم ۲^n در مبنای ۱۰ و بنابراین جواب با radix sort برابر
(۱۰+n) ضربدر logn
ایا درست فکر می کنم و ایا واقعا هیچ الگوریتمی با زمان اجرا n برای مسئله وجود دارد
شما را به خدا یکی حواب این سوال بده
(۲۹ دى ۱۳۹۰ ۰۹:۵۷ ب.ظ)rad.bahar نوشته شده توسط: شما را به خدا یکی حواب این سوال بده
سلام دوست عزیز
قبل از هر چیز ذکر چنتا نکته خالی از لطف نیست:
۱- مرتبه مرتب سازی Radixsort برابر است با [tex]\Theta (d(n k))[/tex] میباشد که:
d تعداد ارقام
k محدوده هر رقم
و n هم تعداد ارقام هست .
۲- حالا همین مربته را برای ارقام باینری باز نویسی میکنیم بنابراین:
اگر n عدد b بیتی داشته باشیم الگوریتم مرتب سازی RadixSort این ادعداد را در مرتبه [tex]\Theta ((b/r)(n 2^{r}))[/tex]
مرتب خواهد کرد که:
r تعداد بیتهای هر رقم میباشد .
تعداد ارقام (d):
[tex]b/r[/tex]
و محدوده هر رقم:
[tex]2^{r}[/tex] میباشد .
و اما جواب سئوال شما:
از انجا که برای نشان دادن اعداد در بازده ۰ تا [tex]n^{2}-1[/tex] به [tex]lgn^{2} = 2lgn[/tex] بیت
نیاز داریم لذا با انتخاب [tex]b=2lgn[/tex] و [tex]r = lgn[/tex] داریم: ::
[tex]b/r(n 2^{r}) = \frac{2lgn}{lgn}(n 2^{lgn}) = 2(n n)=2(2n)= 4n =\Theta(n)[/tex]
تمام ماجرا همین بود امیدوارم متوجه شده باشین
در اخر استدلات خودتان هم در مبنای ۱۰ شایان توجه و درست است .
موفق باشین .