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

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

ارسال:
  

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]

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  فناوری اطلاعات سال ۸۴- آرایه - انتقال اندیس؟! Ametrine ۸ ۱,۴۷۳ ۱۵ آبان ۱۳۹۳ ۰۹:۳۵ ب.ظ
آخرین ارسال: Ametrine
  درخت جستجوی دودویی(دولتی ۷۹) tarane1992 ۲ ۷۴۸ ۱۷ دى ۱۳۹۲ ۱۰:۰۹ ب.ظ
آخرین ارسال: tarane1992
  جدول درهم سازی(دولتی ۸۲) tarane1992 ۷ ۱,۹۷۹ ۱۵ دى ۱۳۹۲ ۰۹:۰۵ ب.ظ
آخرین ارسال: soheila2012
  IT دولتی ۸۴ RadMan ۱ ۷۴۲ ۲۲ آبان ۱۳۹۲ ۰۲:۱۴ ق.ظ
آخرین ارسال: rad.bahar
  مهندسی کامپیوتر-دولتی ۸۹ tabassomesayna ۴ ۱,۵۰۶ ۲۵ مهر ۱۳۹۲ ۱۱:۲۰ ق.ظ
آخرین ارسال: tabassomesayna
  مهندسی کامپیوتر-دولتی ۸۲ tabassomesayna ۱ ۹۵۷ ۲۳ مهر ۱۳۹۲ ۰۲:۵۸ ب.ظ
آخرین ارسال: bahman2000
  علوم کامپیوتر دولتی ۸۲ tabassomesayna ۲ ۱,۱۲۱ ۰۸ شهریور ۱۳۹۲ ۰۱:۲۹ ب.ظ
آخرین ارسال: tabassomesayna
  یکسان بودن اولین گره LRV و آخرین گره LVR ؟( دولتی علوم ۸۵) m@hboobe ۸ ۲,۰۵۹ ۱۸ بهمن ۱۳۹۱ ۰۷:۰۱ ب.ظ
آخرین ارسال: asiehmohammadian
  درخت جستجوی دودویی -- دولتی ۷۴ egm1176 ۵ ۱,۴۶۵ ۱۶ بهمن ۱۳۹۱ ۰۱:۵۱ ق.ظ
آخرین ارسال: mahdiii
  درخت جستجوی دودویی -- دولتی ۷۴ egm1176 ۱ ۹۳۵ ۱۳ بهمن ۱۳۹۱ ۰۴:۴۴ ب.ظ
آخرین ارسال: csharpisatechnology

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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