(۲۴ بهمن ۱۳۹۱ ۱۲:۴۲ ب.ظ)MajidManesht2012 نوشته شده توسط: (24 بهمن ۱۳۹۱ ۱۲:۰۳ ب.ظ)arta.66 نوشته شده توسط: در مورد سوال ۵۰ اگه nk نشه یعنی من هیچی از این رشته و مجانبها نفهمیدم!! ببین دوستی که میگی میشه nlogk و استناد میکنی به کتاب دکتر قدسی - nlgn با دnlgk یه دنیا فرقشه چون این دوتا کامل از هم مستقلا وقتی صورت سوال میگه اعداد در بازه n^k تا ۰ یعنی اگه حتی k مساوی ۱۰۰۰۰ هم باشه مرتبه میشه خطی میشه!! ولی با تفسیر شما دیگه خطی نیست!!! شک نکنید که جواب nk هستش اگه ۱ درصدم جواب نباشه جواب n میشه نه اونی که شما میگی چون لگاریتم توو این مبحث بی معنیه چون مقایسه ای درکار نیست
شما معلومه که اصلا" ساختمان داده بلد نیستی، تو کتاب ساختمان دکتر قدسی گفته برای اعداد در بازه ۱ تا nlogn میشه با O(nloglogn) مرتب کرد حالا نگاه کن بین ۱ تا nk من حالا به جای logn داخلی تو اون قبلیه K میزارم دقت کن، میشه nlogK ببین عزیزم اینجا دوتا log داریم! گرفتی؟
اون برادر ...ک میگی سوال گفته مرتب سازی پایه کجا نوشته چرا از خودت حرف در میاری، چشاتو خوب باز کن، تازه یه نکته کنکوری بهتون بگم هروقت تو گزینه ها nlogk دیدین همونو بزنین چون این سوالا مال دکتر قدسی کاملا هم مشخصه
تازه تو سوال هیچ صحبتی از مستقل بودن K نکرده یعنی اگر شما به جای K بیای n بزاری مسلما" اون گزینه ۳ میشه
O(n2) که بدتر از همه گزینه هاست پس مسلما" nk نمیشه. و همینطور اگر K رو
n2 بگیری گزینه ۲ رد میشه پس میمونه گزینه ۱ و ۴ که گزینه ۱ نمیشه چون اگر بگیم Radix زده پس مرتبه Radix میدونی که میانگین برای n تا عدد در بازه ۱ تا
nk میشه
Θ(k(nn))=Θ(2kn)=Θ(nk) پس به هیچ وجه گ ۱ نمیشه حالا تازه فرض کردیم که K مستقل از n باشه یعنی خوشبینانه نگاه کردیم ولی بچه ها یه چیز دیگه هم هست اینه که این سوال اصلا ربطی به Radix نداره چون این سوالا مال فصل مرتب سازی خارجی دکتر قدسی خ تابلو هم هست همون nlogk درسته! یاحق