سلام دوستان
سوال ۹۰ فناوری اطلاعات ۹۰ که بصورت زیر است را ملاحظه بفرمایید مگر تعداد اعداد بالاخره n تا نیست و مگر نباید جواب گزینه ۱ بشود در صورتیکه پاسخ گزینه ۴ است
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سوال زیر نیز مربوط به فناوری اطلاعات ۸۸ است و پاسخ گزینه ۲ است علت را گفته چون مرتب سازی Radix از مرتبه s*n است اینجا s ثابت است در صورتیکه s وابسته به n است!!!!!!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
و سوال آخر اینکه در کتاب مقسمی یک سوال مولف بصورت زیر است
T را به روش بین ترتیب پیمایش کن و عناصر را به همین ترتیب در خروجی بنویس مرتبه زمان اجرای این الگوریتم به ترتیب در بهترین حالت، بدترین حالت و حالت متوسط کدام است؟
جواب : O(n logn) O(n2) O(n logn)
مگر تمام پیماشها از مرتبه O(n) نیستند؟؟؟؟
جواب سوال اولی که radix sort هست به نظر من میشه گزینه ۲ . یعنی پارسه گزینه ۲ زده
شما فرض کن مبنا مساوی ۱۰ هستش پس میتونیم نتیجه بگیریم که اعداد از ۰ تا n-1 هستن دیگه
۰-۱-۲-۳-۴-۵-۶-۷-۸-۹ ( چرا ؟ چون بیشتر از ۱۰ که دیگه مبنا ده دهی نمیشه )
درست ؟
حالا این گفته ۰ تا n^2-1 یعنی ۲ بار مرتب سازی رو اعمال کرده که هر بار بازه اعداد ۰ تا n-1 بوده
حالا تو هر بار مرتب سازی متوسط زمان اجرا میشه (O(n . پس کل زمان اجرا میشه ( ۲ بار radix )
(O(n+n که میشه (O(n
(۲۴ دى ۱۳۹۳ ۰۱:۰۴ ب.ظ)ardaaalan نوشته شده توسط: جواب سوال اولی که radix sort هست به نظر من میشه گزینه ۲ . یعنی پارسه گزینه ۲ زدهبله جواب ۲ است اشتباه تایپی من است که ۴ زدم ولی منظورم همین بود که ۲ جواب نمیشه مگر الگوریتم به تعداد ارقام عدد تکرار نمیشه؟؟خب وقتی اعداد در بازه ۰ تا n2-1 است بالاخره تعداد ارقام مشخص نیست مثلا اگر n=1000 باشد تعداد ارقام آن ۰تا ۷ است ؟
شما فرض کن مبنا مساوی ۱۰ هستش پس میتونیم نتیجه بگیریم که اعداد از ۰ تا n-1 هستن دیگه
۰-۱-۲-۳-۴-۵-۶-۷-۸-۹ ( چرا ؟ چون بیشتر از ۱۰ که دیگه مبنا ده دهی نمیشه )
درست ؟
حالا این گفته ۰ تا n^2-1 یعنی ۲ بار مرتب سازی رو اعمال کرده که هر بار بازه اعداد ۰ تا n-1 بوده
حالا تو هر بار مرتب سازی متوسط زمان اجرا میشه (O(n . پس کل زمان اجرا میشه ( ۲ بار radix )
(O(n+n که میشه (O(n
در مورد قسمت اول سوالتون که مییگین باید بگم که تو الگوریتم radix sort ما اصلاً بازه ای از ۰ تا n^2-1 نداریم . این نشون میده که مرتب سازی radix sort 2 بار روی الگوریتم تکرار شده . چون تو هر بار radix مرتب سازی روی آرایه های ۰ تا n-1 آنجام میگیره و اینکه تو radix sort بله به تعداد ارقام عدد مرتب سازی تکرار میشه .
بهتره اینطوری بگم
تو radix زمان اجرامون برابر با چیه ؟؟ (O(n+r
خوب
حالا اینجا n آرایمونه که از فاصله ۰ تا n-1 هستش
حالا r هم پایمونه . پایمونم برابر n هستش . خوب تو زمان اجرای بالا بزاری ۱ بار مرتب سازی زمان (O(n صرف میکنه
۲ بار مرتب سازی انجام شده . ۲ بار (O(n که میشه (O(n+n
حالا بازم تحلیل من و اون چیزی که خوندم اینو میگه . نمیدونم در چه حد درست یا غلط باشه