این سوال یعنی اینکه 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 نوشته شده توسط:  سوال که بیان شده سوال الگوریتم سال ۸۴ هست نه سوال ساختمان

بله، اشتباه از من بود.