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

atharrashno پرسیده:

تست ۶۶ طراحی الگوریتم گرایش هوش مصنوعی سال ۸۳

این سوا در مورد پیچیدگی بهترین الگوریم برای الگوریم داده شذه است که میشه ثابت کرد قطعا از درجه nlogk
است اما انچه که یاعث شبهناک بودنه گزینه ۱ و ۳ هست
حالت متوسط nlogk
یا همیشه از درجه nlogk است در مفهوم چه فرقی دارند

اقای مقسمی گزینه ۱ را زدند
اقای قلی زاده گزینه ۳ را زدند.
!!


فایل‌(های) پیوست شده

مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

hadi_m پاسخ داده:

RE: طراحی الگوریم گرایش هوش مصنوعی سال ۸۳ سوال ۶۶

با سلام
اول از لحاظ مفهمی:
وقتی میگه حالت متوسط یعنی میتونه مرتبه یا هزینه ما بیشتر از این مقدار هم بشه اما وقتی میگه همیشه یعنی چه در در حالت بدترین و چه در حالت متوسط یا بهترین همیشه همین مقدار را باید هزینه کنیم.
و اما در ادامه ...
بگذارید اینجور توضیح بدم که فرض کنید این همان الگرویتم مرتب سازی سریع است .
توضیح: در مرتب سازی سریع ما تا زمانی که به ارایه های تک عضوی برسیم مراحل تقسیم و پارتیشن بندی را انجام میدهیم .
حال اینطور تصور کنید که این الگوریتم وقتی به ارایه هایی به طول [tex]\frac{N}{K}[/tex]
رسید دیگر پارتیشن بندی را متوقف کرده و کار تمام شده است .
محاسبه پیچدگی:
در این الگروریتم هر بار هزینه پارتیشن بندی را داریم [tex]O(n)[/tex]
اما عمق درخت از Lgn به Lgk کاهش پیدا میکند زیرا:
تعداد گره‌ها در برگها برابر با [tex]\frac{N}{K}[/tex] میباشد .(در مرتب سازی سریع تا ۱ پیش میرفتیم )و لذا داریم: :

[tex]\frac{N}{2^{h}}= \frac{N}{K} \Rightarrow h=log(k)[/tex]

و در نهایت همیشه مرتبه ان برابر است با‌ ::[tex]Nlog(k)[/tex]

نکته اخر بر سر اختلاف نظر بزرگان در حل این تست:
همانطور که میدانید کارایی مرتب سازی سریع به نحوه پارتیشن بندی بستگی دارد اگر پارتیشن بندی به طرز مناسبی صورت گیرد لذا مرتب سازی سریع همیشه nlgn است و همانطور که میدانید در بدترین حال از مرتبه ۲ است اما الگوریتمهایی وجود دارندکه با انتخاب عنصر محور مناسب جهت پارتیشن بندی (روش میانه سه و یا انتخاب تصادفی) همواره هزینه nlgn را دارند و لذا هزینه ان همیشه nlgn است (برای اثبات قضیه به کتاب Clrs مراجعه کنید.)
تمام ماجرا همین بود
موفق باشید.

۰
ارسال:
  

Sunshine Off پاسخ داده:

RE: طراحی الگوریم گرایش هوش مصنوعی سال ۸۳ سوال ۶۶

جواب این سوال گزینه ۱ میشه حالا چرا؟
nعنصر داریم که میخواهیم آنها رابهkمجموعه پارتیشن کنیم که همه عناصر مجموعه اول از همه عناصر مجموعه دوم،همه عناصرمجموعه دوم از همه عناصر مجموعه سوم و...کوچکترهستند.برای اینکار ابتدا میانه راپیداکرده که هزینه آنO(n وروی آنpivot میزنیم دراینصورت همه عناصر سمت چپ ازآن کوچکتر وهمه عناصرسمت راست ازآن بزرگترهستند(درواقع انکاردوتا مجموعه ساختیم)سپس دوباره همین اعمال را روی زیر آرایه‌ها انجام میدیمیعنی میانه هرزیر آرایه رابدست میاوریم وتا آخر...وقتی kتا مجموعه داریم باید log k بار آرایه رابشکنیم وچون هزینه هر سطرO(n پس در مجموع همیشه از مرتبهnlogkهست.امیدوارم متوجه شده باشید.Shy

۰
ارسال:
  

atharrashno پاسخ داده:

طراحی الگوریم گرایش هوش مصنوعی سال ۸۳ سوال ۶۶

خوب پس بزارید ببینیم من درست متوجه شدم یا نه:
درسته الگوریتم سریع در بدتریت حات درجهn^2 را داره اما باید دید طراح احتمال وقوع بدترین ورودی را در نظر داشته است با خیر اگر فرض طراح randomized _quick sort (یا هر الگوریتم انتخاب تصادفی میانه) باشد
باید گفت بدترین حالت چون رخ نمیدهد (یا با احتمال خیلی کم )پس همیشه از درجه nlog n میباشد
و در این سوال گزینه همیشه از درجه nlog k _با همون در نظر داشتن فرض بالا _انتخاب میشه.
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

atharrashno پاسخ داده:

طراحی الگوریم گرایش هوش مصنوعی سال ۸۳ سوال ۶۶

دوست متین من متوجه شده بودم و اصلش اینه که جواب را بدست اورده بودم اما نمی فهمیدم که همیشه از درجه nlogk با به طور متوسط از درجه nlog k چه فرقی دارند که با توضیحات دوستان اونم برطرف شد و به گزیه همیشه از درجه nlogk روی اوردم!
مشاهده‌ی وب‌سایت کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پاسخنامه تشریحی طراحی الگوریتم موسسه ماهان برای درس طراحی الگوریتم کنکور ۹۱ مهندسی MSsoftware ۸ ۶,۱۲۵ ۰۴ بهمن ۱۳۹۱ ۱۲:۰۲ ق.ظ
آخرین ارسال: fa_karoon
  تست ۳۸ طراحی الگوریتم سال ۸۵ پشتکار ۱۰ ۲,۸۴۹ ۲۹ دى ۱۳۹۱ ۰۹:۲۴ ب.ظ
آخرین ارسال: csharpisatechnology
  تست ۴۰ طراحی الگوریتم نرم افزار ۸۶ reyhaneh64 ۲ ۱,۶۰۲ ۲۹ دى ۱۳۹۱ ۰۲:۱۲ ب.ظ
آخرین ارسال: csharpisatechnology
  بررسی سوالات طراحی الگوریتم ۹۱ مهندسی کامپیوتر -گرایش هوش fatima1537 ۸۶ ۳۰,۱۴۵ ۲۰ اسفند ۱۳۹۰ ۰۹:۴۰ ب.ظ
آخرین ارسال: anyone
  تست (مرتبه اجرایی ) طراحی الگوریتم کنکور ۹۱ vijay ۷ ۳,۱۶۸ ۱۵ اسفند ۱۳۹۰ ۰۵:۳۴ ب.ظ
آخرین ارسال: لهمشد
  بررسی سوالات طراحی الگوریتم ۹۱ فناوری اطلاعات uniquegirl ۲۸ ۷,۹۷۵ ۰۶ اسفند ۱۳۹۰ ۱۱:۲۶ ب.ظ
آخرین ارسال: rotbe
  تست (گراف) طراحی الگوریتم آی تی کنکور ۹۱ vijay ۴ ۲,۶۹۴ ۰۱ اسفند ۱۳۹۰ ۰۶:۴۰ ق.ظ
آخرین ارسال: MSZ
  تست مرتبه اجرایی طراحی الگوریتم کنکور ۹۱ vijay ۲ ۲,۴۲۳ ۳۰ بهمن ۱۳۹۰ ۰۱:۵۴ ب.ظ
آخرین ارسال: arixooo
  تست ۳۲ طراحی الگوریتم سال ۹۰ Anahita.R ۳ ۲,۰۶۱ ۲۶ بهمن ۱۳۹۰ ۱۱:۳۶ ق.ظ
آخرین ارسال: atharrashno
  سوال هوش مصنوعی ۱۳۸۷ lonelyforever ۱ ۸۶۵ ۲۶ بهمن ۱۳۹۰ ۱۱:۲۴ ق.ظ
آخرین ارسال: fatima1537

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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