سلام
این سئوال کنکور سال ۸۴ است:
میخواهیم k تا کوچکترین عناصر یک آرایه را از کوچک به بزرگ به صورت مرتب به دست آوریم. کدام یک از الگوریتم های زیر درست و سریع‌تر از بقیه است؟
۱) عناصر را مرتب میکنیم و سپس kتای اول آن را به ترتیب بر میداریم.
۲) یک Heap بر روی این عناصر میسازیم و سپس kبار کوچکترین عنصر را به دست می آوریم.
۳) kامین عنصر را انتخاب میکنیم. این عنصر را محور قرار داده و عمل بخش پذیری را انجام میدهیم و سپس کار را دنبال میکنیم.
۴) عنصر میانه را به دست آورده و براساس این محور عمل بخش بندی را انجام میدهیم. سپس در یکی از بخش‌ها کار را دنبال میکنیم.
این سئوال کنکور سال ۸۴ است:
میخواهیم k تا کوچکترین عناصر یک آرایه را از کوچک به بزرگ به صورت مرتب به دست آوریم. کدام یک از الگوریتم های زیر درست و سریع‌تر از بقیه است؟
۱) عناصر را مرتب میکنیم و سپس kتای اول آن را به ترتیب بر میداریم.
۲) یک Heap بر روی این عناصر میسازیم و سپس kبار کوچکترین عنصر را به دست می آوریم.
۳) kامین عنصر را انتخاب میکنیم. این عنصر را محور قرار داده و عمل بخش پذیری را انجام میدهیم و سپس کار را دنبال میکنیم.
۴) عنصر میانه را به دست آورده و براساس این محور عمل بخش بندی را انجام میدهیم. سپس در یکی از بخش‌ها کار را دنبال میکنیم.
کلید سئوال گزینه‌ی ۳ است.
اولاً: چرا ۳؟
ثانیاً: عمل بخش پذیری یعنی چی؟
ثالثاً: مرتبه‌ی الگوریتم های داده شده در گزینه‌ها چی هستند؟
این سوال یعنی اینکه k بار الگوریتم kامین کوچکترین عنصر رو اجرا میکنیم خوب مثلا شما میخوای ارایه ۱۰ عنصری رو ۳ عنصر اولش رو مرتب کنی K=3 یک بار الگوریتم kامین کوچکترین عنصر رو به ازای k=3 صدا میزنی که سومین عنصر کوچک میاد خونه سوم حالا دوباره به ازای k=2 و دوباره دومین عنصر کوچک میاد خونه دوم به ازای k=1 میبینی کوچکترین عنصر میاد خونه اول.که ۳ تا عنصری که از همه کوچکترند در اول ارایه به صورت مرتب صعودی قرار می گیرند.حالا شما k بار داری یک الگوریتم رو که از مرتبه n هستش صدا میزنی که اگه n وk خیلی بزرگ باشه مرتبه میشه nk حالا تو این مورد خاص که k خیلی کوچک هستش میشه از k صرف نظر کرد.
گزینه ۱ که مشخصه مرتبه nlogn
گزینه دوم هیپ که ساخته میشه خودش مرتبه داره هربار که کوچکترین عنصر رو هم حذف کنیم دوباره باید هیپ رو ترمیم کنیم
گزینه چهارم هم خودش از مرتبه الگوریتم مرتب سازی سریع هستش پس بهترین گزینه میتونه همون ۳ باشه که توضیحاتش رو دادم
(۲۸ آذر ۱۳۸۹ ۰۳:۱۸ ب.ظ)javadjj نوشته شده توسط: این سوال یعنی اینکه k بار الگوریتم kامین کوچکترین عنصر رو اجرا میکنیم خوب مثلا شما میخوای ارایه ۱۰ عنصری رو ۳ عنصر اولش رو مرتب کنی K=3 یک بار الگوریتم kامین کوچکترین عنصر رو به ازای k=3 صدا میزنی که سومین عنصر کوچک میاد خونه سوم حالا دوباره به ازای k=2 و دوباره دومین عنصر کوچک میاد خونه دوم به ازای k=1 میبینی کوچکترین عنصر میاد خونه اول.که ۳ تا عنصری که از همه کوچکترند در اول ارایه به صورت مرتب صعودی قرار می گیرند.حالا شما k بار داری یک الگوریتم رو که از مرتبه n هستش صدا میزنی که اگه n وk خیلی بزرگ باشه مرتبه میشه nk حالا تو این مورد خاص که k خیلی کوچک هستش میشه از k صرف نظر کرد.
گزینه ۱ که مشخصه مرتبه nlogn
گزینه دوم هیپ که ساخته میشه خودش مرتبه داره هربار که کوچکترین عنصر رو هم حذف کنیم دوباره باید هیپ رو ترمیم کنیم
گزینه چهارم هم خودش از مرتبه الگوریتم مرتب سازی سریع هستش پس بهترین گزینه میتونه همون ۳ باشه که توضیحاتش رو دادم
آخه اینجا که حرفی نزده که k کوچیکه! اتفاقاً من بدترین حالت همه اش رو در نظر گرفتم!
گزینه‌ی ۱: بدترین حالت nlogn (البته بدترین حالت با بهترین الگوریتم مرتب سازی)
گزینه‌ی ۲: بدترین حالت nlogn+klogn که k در بدترین حالت n خواهد بود پس میشه nlogn!
گزینه‌ی ۳: بدترین حالت k برابر با n است پس میشه n^2
گزینه‌ی ۴: همون طور که گفتید مرتب سازی سریع است و در بدترین حالت میشه n^2
پس به نظر من باید یا گزینه‌ی یک بشه یا دو! که البته هیچکدوم جواب نیست!!! به نظر من گزینه‌ی ۲ در هر صورت بهترینه...
ببینید یک رابطه تو kامین کوچکترین عنصر هست که اگه جایگذاری کنید می بینید که گزینه ۳ همون n میشه حتی اگه k مساوی nباشه ببینید ما هر بار داریم الگوریتم kامین کوچکترین عنصر رو جدا اجرا میکنیم.(عامیانه حرف بزنم k تو خوده برنامه kامین کوچکترین دخیل نیستش.)برای همین میشه ازش کاملا صرف نظر کرد مثلا اینجوری نیست که k تو برنامه تاثیر خودش رو بصورت یک حلقه تو درتو بزاره که توان مرتبه رو اضافه کنه.
جواب این تست گزینه یک هست اشتباه شده گزینه ۳ توی کتاب تست هاست که اشتباهه گزینه یک درسته
توی سایت دکتر قدسی هم یک زده
(۳۰ دى ۱۳۹۰ ۰۴:۱۷ ب.ظ)saba1000 نوشته شده توسط: جواب این تست گزینه یک هست اشتباه شده گزینه ۳ توی کتاب تست هاست که اشتباهه گزینه یک درستهگزینه ۳ صحیح است
توی سایت دکتر قدسی هم یک زده
گزینه اول در حالت میانگین حداقل به زمان nlog n نیاز داره
اما گزینه ۳ اول در زمان (O(n عنصر k را یافته و عمل پارتیشن انجام میدهد سپس با یه الگوریتم مرتب سازی اون k عنصر رو در زمان klogk مرتب میکنیم که در حالت میانگین از روش اول سریع‌تر است (البته بسته به مقدار k این سرعت بیشتر محدود به یک عدد ثابت میشه یعنی اینکه مرتبه گزینه ۱و ۳ یکسان هست ). اما در بدترین حالت هر دو روش دارای پیچیدگی یکسان خواهند بود( حالت n=k )اما گزینه ۳ کند تره چراکه یک عمل پارتیشن اضافی انجام داده .
این سوال سایت دکتر قدسی که من نگاه کردم از کنکور ۸۴ حذف نشده و گزینه ۱ هم جواب هست به اونجا یه سر بزنید به نظر من هم یک درسته
(۳۰ دى ۱۳۹۰ ۰۸:۰۸ ب.ظ)saba1000 نوشته شده توسط: این سوال سایت دکتر قدسی که من نگاه کردم از کنکور ۸۴ حذف نشده و گزینه ۱ هم جواب هست به اونجا یه سر بزنید به نظر من هم یک درسته.سوال ۵۱ سال ۸۴ هستش و اونجا هم ۳ اعلام شده.
گزینه ۳ میشه klogk
در در بدترین حالت k=n ........
درسته که میشه nlogn ولی سوال بدترین حالت رو نخواسته...! درست ترین و سریع ترین گزینه ۳ است....!
سوال که بیان شده سوال الگوریتم سال ۸۴ هست نه سوال ساختمان
(۳۰ دى ۱۳۹۰ ۱۰:۳۷ ب.ظ)saba1000 نوشته شده توسط: سوال که بیان شده سوال الگوریتم سال ۸۴ هست نه سوال ساختمانبله، اشتباه از من بود.