شما را به خدا یکی حواب این سوال بده

(۲۹ دى ۱۳۹۰ ۰۹:۵۷ ب.ظ)rad.bahar نوشته شده توسط:  شما را به خدا یکی حواب این سوال بده

سلام دوست عزیز
قبل از هر چیز ذکر چنتا نکته خالی از لطف نیست:
۱- مرتبه مرتب سازی Radixsort برابر است با $\Theta (d(n k))$ میباشد که:
d تعداد ارقام
k محدوده هر رقم
و n هم تعداد ارقام هست .

۲- حالا همین مربته را برای ارقام باینری باز نویسی میکنیم بنابراین:
اگر n عدد b بیتی داشته باشیم الگوریتم مرتب سازی RadixSort این ادعداد را در مرتبه $\Theta ((b/r)(n 2^{r}))$
مرتب خواهد کرد که:
r تعداد بیتهای هر رقم میباشد .
تعداد ارقام (d):
$b/r$
و محدوده هر رقم:
$2^{r}$ میباشد .

و اما جواب سئوال شما:
از انجا که برای نشان دادن اعداد در بازده ۰ تا $n^{2}-1$ به $lgn^{2} = 2lgn$ بیت
نیاز داریم لذا با انتخاب $b=2lgn$ و $r = lgn$ داریم: ::

$b/r(n 2^{r}) = \frac{2lgn}{lgn}(n 2^{lgn}) = 2(n n)=2(2n)= 4n =\Theta(n)$

تمام ماجرا همین بود امیدوارم متوجه شده باشین

در اخر استدلات خودتان هم در مبنای ۱۰ شایان توجه و درست است .
موفق باشین .