زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۷:۵۹ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

Kتا عنصر اول یک آرایه - فصل مرتب سازی

ارسال:
  

Mansoureh پرسیده:

Kتا عنصر اول یک آرایه - فصل مرتب سازی

سلام
این سئوال کنکور سال ۸۴ است:
میخواهیم k تا کوچکترین عناصر یک آرایه را از کوچک به بزرگ به صورت مرتب به دست آوریم. کدام یک از الگوریتم های زیر درست و سریع‌تر از بقیه است؟
۱) عناصر را مرتب میکنیم و سپس kتای اول آن را به ترتیب بر میداریم.
۲) یک Heap بر روی این عناصر میسازیم و سپس kبار کوچکترین عنصر را به دست می آوریم.
۳) kامین عنصر را انتخاب میکنیم. این عنصر را محور قرار داده و عمل بخش پذیری را انجام میدهیم و سپس کار را دنبال میکنیم.
۴) عنصر میانه را به دست آورده و براساس این محور عمل بخش بندی را انجام میدهیم. سپس در یکی از بخش‌ها کار را دنبال میکنیم.


کلید سئوال گزینه‌ی ۳ است.
اولاً: چرا ۳؟
ثانیاً: عمل بخش پذیری یعنی چی؟
ثالثاً: مرتبه‌ی الگوریتم های داده شده در گزینه‌ها چی هستند؟

۰
ارسال:
  

javadjj پاسخ داده:

Kتا عنصر اول یک آرایه - فصل مرتب سازی

این سوال یعنی اینکه k بار الگوریتم kامین کوچکترین عنصر رو اجرا میکنیم خوب مثلا شما میخوای ارایه ۱۰ عنصری رو ۳ عنصر اولش رو مرتب کنی K=3 یک بار الگوریتم kامین کوچکترین عنصر رو به ازای k=3 صدا میزنی که سومین عنصر کوچک میاد خونه سوم حالا دوباره به ازای k=2 و دوباره دومین عنصر کوچک میاد خونه دوم به ازای k=1 میبینی کوچکترین عنصر میاد خونه اول.که ۳ تا عنصری که از همه کوچکترند در اول ارایه به صورت مرتب صعودی قرار می گیرند.حالا شما k بار داری یک الگوریتم رو که از مرتبه n هستش صدا میزنی که اگه n وk خیلی بزرگ باشه مرتبه میشه nk حالا تو این مورد خاص که k خیلی کوچک هستش میشه از k صرف نظر کرد.
گزینه ۱ که مشخصه مرتبه nlogn
گزینه دوم هیپ که ساخته میشه خودش مرتبه داره هربار که کوچکترین عنصر رو هم حذف کنیم دوباره باید هیپ رو ترمیم کنیم
گزینه چهارم هم خودش از مرتبه الگوریتم مرتب سازی سریع هستش پس بهترین گزینه میتونه همون ۳ باشه که توضیحاتش رو دادم

ارسال:
  

Mansoureh پاسخ داده:

RE: Kتا عنصر اول یک آرایه - فصل مرتب سازی

(۲۸ آذر ۱۳۸۹ ۰۳:۱۸ ب.ظ)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


پس به نظر من باید یا گزینه‌ی یک بشه یا دو! که البته هیچکدوم جواب نیست!!! به نظر من گزینه‌ی ۲ در هر صورت بهترینه...
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

javadjj پاسخ داده:

Kتا عنصر اول یک آرایه - فصل مرتب سازی

ببینید یک رابطه تو kامین کوچکترین عنصر هست که اگه جایگذاری کنید می بینید که گزینه ۳ همون n میشه حتی اگه k مساوی nباشه ببینید ما هر بار داریم الگوریتم kامین کوچکترین عنصر رو جدا اجرا میکنیم.(عامیانه حرف بزنم k تو خوده برنامه kامین کوچکترین دخیل نیستش.)برای همین میشه ازش کاملا صرف نظر کرد مثلا اینجوری نیست که k تو برنامه تاثیر خودش رو بصورت یک حلقه تو درتو بزاره که توان مرتبه رو اضافه کنه.

۰
ارسال:
  

saba1000 پاسخ داده:

Kتا عنصر اول یک آرایه - فصل مرتب سازی

جواب این تست گزینه یک هست اشتباه شده گزینه ۳ توی کتاب تست هاست که اشتباهه گزینه یک درسته
توی سایت دکتر قدسی هم یک زده
مشاهده‌ی وب‌سایت کاربر

ارسال:
  

Masoud05 پاسخ داده:

RE: Kتا عنصر اول یک آرایه - فصل مرتب سازی

(۳۰ دى ۱۳۹۰ ۰۴:۱۷ ب.ظ)saba1000 نوشته شده توسط:  جواب این تست گزینه یک هست اشتباه شده گزینه ۳ توی کتاب تست هاست که اشتباهه گزینه یک درسته
توی سایت دکتر قدسی هم یک زده
گزینه ۳ صحیح است
گزینه اول در حالت میانگین حداقل به زمان nlog n نیاز داره
اما گزینه ۳ اول در زمان (O(n عنصر k را یافته و عمل پارتیشن انجام میدهد سپس با یه الگوریتم مرتب سازی اون k عنصر رو در زمان klogk مرتب میکنیم که در حالت میانگین از روش اول سریع‌تر است (البته بسته به مقدار k این سرعت بیشتر محدود به یک عدد ثابت میشه یعنی اینکه مرتبه گزینه ۱و ۳ یکسان هست ). اما در بدترین حالت هر دو روش دارای پیچیدگی یکسان خواهند بود( حالت n=k )اما گزینه ۳ کند تره چراکه یک عمل پارتیشن اضافی انجام داده .
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

saba1000 پاسخ داده:

Kتا عنصر اول یک آرایه - فصل مرتب سازی

این سوال سایت دکتر قدسی که من نگاه کردم از کنکور ۸۴ حذف نشده و گزینه ۱ هم جواب هست به اونجا یه سر بزنید به نظر من هم یک درسته
مشاهده‌ی وب‌سایت کاربر

ارسال:
  

shervinrs پاسخ داده:

RE: Kتا عنصر اول یک آرایه - فصل مرتب سازی

(۳۰ دى ۱۳۹۰ ۰۸:۰۸ ب.ظ)saba1000 نوشته شده توسط:  این سوال سایت دکتر قدسی که من نگاه کردم از کنکور ۸۴ حذف نشده و گزینه ۱ هم جواب هست به اونجا یه سر بزنید به نظر من هم یک درسته.
سوال ۵۱ سال ۸۴ هستش و اونجا هم ۳ اعلام شده.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

variant20002000 پاسخ داده:

Kتا عنصر اول یک آرایه - فصل مرتب سازی

گزینه ۳ میشه klogk
در در بدترین حالت k=n ........
درسته که میشه nlogn ولی سوال بدترین حالت رو نخواسته...! درست ترین و سریع ترین گزینه ۳ است....!

۰
ارسال: #۱۰
  

saba1000 پاسخ داده:

Kتا عنصر اول یک آرایه - فصل مرتب سازی

سوال که بیان شده سوال الگوریتم سال ۸۴ هست نه سوال ساختمان
مشاهده‌ی وب‌سایت کاربر

ارسال: #۱۱
  

shervinrs پاسخ داده:

RE: Kتا عنصر اول یک آرایه - فصل مرتب سازی

(۳۰ دى ۱۳۹۰ ۱۰:۳۷ ب.ظ)saba1000 نوشته شده توسط:  سوال که بیان شده سوال الگوریتم سال ۸۴ هست نه سوال ساختمان
بله، اشتباه از من بود.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  منابع درسی اول دبیرستان azaaadeh457 ۱ ۱,۰۳۱ ۰۴ دى ۱۴۰۱ ۱۰:۲۱ ب.ظ
آخرین ارسال: HamidReza1
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۲۸۷ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  مرخصی در ترم اول و سپس انصراف MSZ ۱۷ ۳۹,۴۲۷ ۱۷ بهمن ۱۳۹۹ ۰۱:۵۷ ق.ظ
آخرین ارسال: hmaryam567
  تکمیل قطعه کد مجموع آرایه Xzrix ۰ ۱,۲۸۸ ۰۲ دى ۱۳۹۹ ۰۷:۱۹ ب.ظ
آخرین ارسال: Xzrix
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۳۶۸ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۵,۱۴۹ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۳,۸۳۷ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  سئو چیست؟ - سئو - بهینه سازی سایت msnmsn ۲ ۲۴ ۲۳ آبان ۱۳۹۸ ۰۱:۱۳ ب.ظ
آخرین ارسال: xiaomi
  راهنمایی انتخاب واحد ترم اول، ارشد نرم، مباحث بیگ دیتا و دیتابیس arian_61 ۱ ۲,۵۱۸ ۲۵ شهریور ۱۳۹۸ ۱۰:۴۱ ب.ظ
آخرین ارسال: arian_61
  مجموعه آموزش تصویری ابزار شبیه سازی و بررسی پروتکل امنیتی اسکایتر net work ۰ ۲,۳۱۹ ۲۲ فروردین ۱۳۹۸ ۰۳:۲۵ ب.ظ
آخرین ارسال: net work

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close