تالار گفتمان مانشت

سلام دوستان
سوال ۹۰ فناوری اطلاعات ۹۰ که بصورت زیر است را ملاحظه بفرمایید مگر تعداد اعداد بالاخره n تا نیست و مگر نباید جواب گزینه ۱ بشود در صورتیکه پاسخ گزینه ۴ است

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.



سوال زیر نیز مربوط به فناوری اطلاعات ۸۸ است و پاسخ گزینه ۲ است علت را گفته چون مرتب سازی Radix از مرتبه s*n است اینجا s ثابت است در صورتیکه s وابسته به n است!!!!!!

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


و سوال آخر اینکه در کتاب مقسمی یک سوال مولف بصورت زیر است
T را به روش بین ترتیب پیمایش کن و عناصر را به همین ترتیب در خروجی بنویس مرتبه زمان اجرای این الگوریتم به ترتیب در بهترین حالت، بدترین حالت و حالت متوسط کدام است؟
جواب : O(n logn) O(n2) O(n logn)

مگر تمام پیماشها از مرتبه O(n) نیستند؟؟؟؟

جواب سوال اولی که radix sort هست به نظر من میشه گزینه 2 . یعنی پارسه گزینه 2 زده
شما فرض کن مبنا مساوی 10 هستش پس میتونیم نتیجه بگیریم که اعداد از 0 تا n-1 هستن دیگه
0-1-2-3-4-5-6-7-8-9 ( چرا ؟ چون بیشتر از 10 که دیگه مبنا ده دهی نمیشه )
درست ؟
حالا این گفته 0 تا n^2-1 یعنی 2 بار مرتب سازی رو اعمال کرده که هر بار بازه اعداد 0 تا n-1 بوده
حالا تو هر بار مرتب سازی متوسط زمان اجرا میشه (O(n . پس کل زمان اجرا میشه ( 2 بار radix )
(O(n+n که میشه (O(n

(24 دى 1393 01:04 ب.ظ)ardaaalan نوشته شده توسط: [ -> ]جواب سوال اولی که radix sort هست به نظر من میشه گزینه ۲ . یعنی پارسه گزینه ۲ زده
شما فرض کن مبنا مساوی ۱۰ هستش پس میتونیم نتیجه بگیریم که اعداد از ۰ تا n-1 هستن دیگه
۰-۱-۲-۳-۴-۵-۶-۷-۸-۹ ( چرا ؟ چون بیشتر از ۱۰ که دیگه مبنا ده دهی نمیشه )
درست ؟
حالا این گفته ۰ تا n^2-1 یعنی ۲ بار مرتب سازی رو اعمال کرده که هر بار بازه اعداد ۰ تا n-1 بوده
حالا تو هر بار مرتب سازی متوسط زمان اجرا میشه (O(n . پس کل زمان اجرا میشه ( ۲ بار radix )
(O(n+n که میشه (O(n

بله جواب 2 است اشتباه تایپی من است که 4 زدم ولی منظورم همین بود که 2 جواب نمیشه مگر الگوریتم به تعداد ارقام عدد تکرار نمیشه؟؟خب وقتی اعداد در بازه 0 تا n2-1 است بالاخره تعداد ارقام مشخص نیست مثلا اگر n=1000 باشد تعداد ارقام آن 0تا 7 است ؟

در مورد قسمت اول سوالتون که مییگین باید بگم که تو الگوریتم radix sort ما اصلاً بازه ای از 0 تا n^2-1 نداریم . این نشون میده که مرتب سازی radix sort 2 بار روی الگوریتم تکرار شده . چون تو هر بار radix مرتب سازی روی آرایه های 0 تا n-1 آنجام میگیره و اینکه تو radix sort بله به تعداد ارقام عدد مرتب سازی تکرار میشه .
بهتره اینطوری بگم
تو radix زمان اجرامون برابر با چیه ؟؟ (O(n+r
خوب
حالا اینجا n آرایمونه که از فاصله 0 تا n-1 هستش
حالا r هم پایمونه . پایمونم برابر n هستش . خوب تو زمان اجرای بالا بزاری 1 بار مرتب سازی زمان (O(n صرف میکنه
2 بار مرتب سازی انجام شده . 2 بار (O(n که میشه (O(n+n
حالا بازم تحلیل من و اون چیزی که خوندم اینو میگه . نمیدونم در چه حد درست یا غلط باشه