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

(۲۹ دى ۱۳۹۰ ۰۹:۵۷ ب.ظ)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]

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

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