زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۶:۳۲ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال ۴۶ دولتی فناوری اطلاعات سال۹۰

ارسال:
  

rad.bahar پرسیده:

سوال ۴۶ دولتی فناوری اطلاعات سال۹۰

کم رشدترین حد بالای زمان اجرای الگوریتم مرتب سازی 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 پاسخ داده:

تست ۴۶ it90

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

ارسال:
  

hadi_m پاسخ داده:

RE: تست ۴۶ it90

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

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  دانلود سوالات تخصصی گرایش فناوری اطلاعات آزمون دکتری ۹۱(کد ۲۳۵۸) Lonely Palm ۲ ۵,۸۶۳ ۲۶ دى ۱۴۰۲ ۰۲:۳۳ ب.ظ
آخرین ارسال: bijibuji
  امریه ارگان های دولتی it_man ۰ ۵۱۶ ۰۸ دى ۱۴۰۱ ۰۱:۵۳ ب.ظ
آخرین ارسال: it_man
Big Grin اطلاعات در مورد دانشگاه تهران (پردیس فارابی) mehRUN ۲ ۴,۳۱۷ ۳۱ شهریور ۱۴۰۱ ۰۱:۴۱ ب.ظ
آخرین ارسال: eng.behnam
  اطلاعات راجع به سیستمهای حضور و غیاب Fingerprint ۱ ۱,۵۵۷ ۰۳ بهمن ۱۴۰۰ ۱۱:۱۴ ب.ظ
آخرین ارسال: Fingerprint
  کارشناسی ارشد فناوری اطلاعات ۱۴۰۱ tablighjonoub ۰ ۱,۴۲۸ ۰۱ دى ۱۴۰۰ ۰۸:۴۳ ب.ظ
آخرین ارسال: tablighjonoub
  منابع برای دکترا -مهندسی فناوری اطلاعات sarit ۱ ۳,۳۲۷ ۱۰ مهر ۱۴۰۰ ۰۸:۵۴ ق.ظ
آخرین ارسال: pouya47
  استخدام در فنآوری اطلاعات خدمات حوزه علمیه قم oloom-ensani ۱۵ ۸,۶۸۹ ۲۴ اردیبهشت ۱۴۰۰ ۰۴:۳۹ ب.ظ
آخرین ارسال: oloom-ensani
  فناوری اطلاعات پزشکی چیست ؟ mahan najafi ۹ ۱۷,۶۸۸ ۱۹ آذر ۱۳۹۹ ۱۲:۲۱ ب.ظ
آخرین ارسال: bahador567
  مصاحبه دانشگاه اطلاعات و امنیت ملی Happiness.72 ۹۸ ۱۰۸,۴۲۰ ۰۵ آذر ۱۳۹۹ ۰۵:۰۵ ب.ظ
آخرین ارسال: Ali001100
  دانلود آموزش تصویری کلاس درس نظریه اطلاعات و کدینگ دانشگاه فردوسی jazana ۵ ۶,۵۳۵ ۰۷ خرداد ۱۳۹۹ ۰۹:۱۰ ق.ظ
آخرین ارسال: hosein92

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close