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

بررسی سوال ۳۳ الگوریتم کنکور نرم ۹۰

subtitle
ارسال:
  

hamidj پرسیده:

بررسی سوال ۳۳ الگوریتم کنکور نرم ۹۰

سلام و خسته نباشید ... دوستان من یک مثال زدم که این سوال خیلی عجیبه که در logn بشه حلش کنیم !
از آنجایی که خودم در تمامی کنکور های آزمایشی پارسه و ... رتبه زیر ۱۰۰ داشتم و در این درس تسلط شدید دارم خواهش میکنم کسانی که تخصص لازم دارن که باعث نشه از بحث دور شیم

در این سوال کمترین هزینه [tex]O(n/2)[/tex] هست که میشه همون [tex]O(n)[/tex]
یک عکس ضمیمه کردم که اینو اثبات میکنه که شما حتما n/2 مقایسه باید انجام بدید

اگر دو آریه وجود نداشت و یک آرایه به صورت صعودی بود آنوقت هزینه k امین عنصر برابر ۱ ... مراجه به اندیس مورد نظر
اما اینجا ۲ آرایه متفاوت هستند به اندازه [tex]n/2[/tex] که k امین عنصر اجتماع آن دو را میخواد در نتیجه میتونه همه جای آرایه قرار بگیره( به عکس مراجعه شود)

هایفل اثبات کرد که حد پایین برای یافتن کوچکترین کلید در مجموعه n کلیدی برای k>1 به صورت زیر است
[tex]n ( k-1 )[ log(n/k-1)] - k [/tex] که برابر میشه با [tex]O(n)[/tex]
page 129 مقسمی

والا کمتر از این من جایی ندیدم کسی موفق شده باشه شاید طراح سوال تونسته یا دانشمندی به تازگی مقاله علمیشو ثبت کرده ما بی اطلاع هستیم !!!!

شاید من اشتباه میکنم اگه روشه حلشو بلدین به منم بگید ممنون میشم


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

۰
ارسال:
  

حامد پاسخ داده:

RE: مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


من خودم چونکه سر جلسه"لوگ کا" توی گزینه‌ها نبود گفتم حتما راه حل بالا مد نظرش نبوده و برای همین گزینه ۴ رو زدم.Confused
من اعتراض کردم.و گزینه "سئوال فاقد گزینه صحیح است" را انتخاب کردم.

۰
ارسال:
  

www پاسخ داده:

مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

با سلام
سوال ۳۳ کاملا درسته تو چند کتاب طراحی الگوریتم هم اورده شده است جواب این سوال همونه رجوع کن به فصل ۲۱ قسمت عملیاتunion,find

۰
ارسال:
  

ف.ش پاسخ داده:

مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

منظورشون کتاب clrs

۰
ارسال:
  

hamidj پاسخ داده:

مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

ببخشید کتاب دیگه ای مد نظرتون هست ... ؟ آخه کتاب کرمن امانت دستم بود پس دادم
کتاب های زیرو دارم

الگوریتم مقسمی
الگوریتم پوران
الگوریتم قلی زاده
ساختمان قدسی
ساختمان پارسه

لطفا صفحه یکی از این کتاب‌ها رو بگید... گرچه همشو میدونم و منم دارم حرف اینارو میزنم... میتونم شماره صفحه بدم
همگی روی n اتفاق نظر دارن

۰
ارسال:
  

poopi پاسخ داده:

RE: مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

این استدلال که میگید می تونه تو همه‌ی خونه‌ها باشه پس باید همه‌ی خونه‌ها مقایسه بشه درست نیست، پس الگوریتم BinarySearch به چه دردی می خوره؟Huh
مثال مشابه اینه که یه آرایه‌ی مرتب با n عنصر داریم و می خوایم ببینیم عدد x در کجای آرایه هست که طبق استدلال شما چون x در همه جای آرایه می تونه باشه پس باید همه‌ی خونه‌ها رو چک کنیم و میشه از [tex]O(n)[/tex] در حالی که می دونیم با یه BS میشه x رو پیدا کرد با [tex]O(log n)[/tex]

الگوریتم با [tex]O(log n)[/tex] یه کم سخته توضیح دادنش اینجا، ولی یه روش واضح با [tex]O(log^{2} n)[/tex] وجود داره به این صورت که فرض می کنیم که kامین عدد در آرایه‌ی A باشه (یکبار هم همین کار رو برای B انجام میدیم) حالا روی آرایه‌ی A الگوریتم BS رو اجرا می کنیم به این صورت که هر بار که یک عنصر میانی در A رو در نظر گرفتیم (فرض کنید [tex]A[i][/tex]) با یه BS دیگه روی B می فهمیم که چندتا از عناصر B از [tex]A[i][/tex] کوچکتر هستند و در نتیجه می تونیم بفهمیم که [tex]A[i][/tex] در صورت ادغام ۲ آرایه عنصر چندم خواهد بود. که اگه از K کمتر بود به سمت اعداد بزرگتر میریم و اگه بیشتر بود بلعکس.
به این ترتیب با ۲ تا BS تو در تو تونستیم kامین عنصر رو پیدا کنیم که میشه از [tex]O (log^{2}n)[/tex]
اگه جاییش نامفهومه بگید توضیح میدم و اگر هم فکر میکنید غلطه ایرادش رو بگید بررسی کنم
اگر هم الگوریتم از [tex]O (logn)[/tex] رو خواستید بگید خلاصه بنویسم

ارسال:
  

hamidj پاسخ داده:

RE: مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

(۱۲ اسفند ۱۳۸۹ ۰۳:۳۳ ق.ظ)poopi نوشته شده توسط:  این استدلال که میگید می تونه تو همه‌ی خونه‌ها باشه پس باید همه‌ی خونه‌ها مقایسه بشه درست نیست، پس الگوریتم BinarySearch به چه دردی می خوره؟Huh
مثال مشابه اینه که یه آرایه‌ی مرتب با n عنصر داریم و می خوایم ببینیم عدد x در کجای آرایه هست که طبق استدلال شما چون x در همه جای آرایه می تونه باشه پس باید همه‌ی خونه‌ها رو چک کنیم و میشه از [tex]O(n)[/tex] در حالی که می دونیم با یه BS میشه x رو پیدا کرد با [tex]O(log n)[/tex]

الگوریتم با [tex]O(log n)[/tex] یه کم سخته توضیح دادنش اینجا، ولی یه روش واضح با [tex]O(log^{2} n)[/tex] وجود داره به این صورت که فرض می کنیم که kامین عدد در آرایه‌ی A باشه (یکبار هم همین کار رو برای B انجام میدیم) حالا روی آرایه‌ی A الگوریتم BS رو اجرا می کنیم به این صورت که هر بار که یک عنصر میانی در A رو در نظر گرفتیم (فرض کنید [tex]A[i][/tex]) با یه BS دیگه روی B می فهمیم که چندتا از عناصر B از [tex]A[i][/tex] کوچکتر هستند و در نتیجه می تونیم بفهمیم که [tex]A[i][/tex] در صورت ادغام ۲ آرایه عنصر چندم خواهد بود. که اگه از K کمتر بود به سمت اعداد بزرگتر میریم و اگه بیشتر بود بلعکس.
به این ترتیب با ۲ تا BS تو در تو تونستیم kامین عنصر رو پیدا کنیم که میشه از [tex]O (log^{2}n)[/tex]
اگه جاییش نامفهومه بگید توضیح میدم و اگر هم فکر میکنید غلطه ایرادش رو بگید بررسی کنم
اگر هم الگوریتم از [tex]O (logn)[/tex] رو خواستید بگید خلاصه بنویسم


خیلی ممنون از گفته هاتون... راستش در مورد ج اولتون که bs به چه دردی میخوره کاملا موافقم اما این سوال یه فرقایی داره آخه لیست باید ادغام بشه در نتیجه لیست باز نا مرتب میشه که توی شکل نشون دادم فرض کن عکسی که دادم آرایه b رو به انتهای a بچسبونیم...... حالا فرض میکنیم( گرچه میدونم که راه درستش اینه که اصلا ادغام نکنیم تا بتونیم پیچدگی کمتری پیدا کنیم و لیست به هم نریزه )که نباید ادغام بشن از روشی که گفتین میریم جلو اما من چند تا مشکل اساسی پیدا کردم که ممنون میشم بازم یه توضیح بدید شاید من بهشون توجه نکردم

۱/ برای پیدا کردن k امین عنصر توی یه لیست مرتب نیازی به جستجوی دودویی نیست و میشه به اندیس مورد نظر روجوع کرد که از [tex]O(1)[/tex] میشه که دیگه نیازی نداری [tex]A[i][/tex] چک کنی که توی آرایه A چندمین عنصر میشه.
۲/ دومین نکته روشی که شما گفتید ما رو به k امین عنصر نمیرسونه( دلیل‌: اول اینکه ما میخواهیم جستجوی دودویی رو با چه مقداری مقایسه کنیم ما که مقادیر آرایه رو نمیدونیم از کجا بدونیم که با چه مقادیری مقایسه بشه (" حالا عکسی رو که پایین دادم بگیرش و نگاش کن و ببینم با چه مقداری جستجوی دودویی میخوای بری و به سومین عنصر برسی.... به فرض یکی از عناصر خود آرایه که [tex]A[i][/tex] باشه..؟ خوب این که فقط تکلیف این خونه رو به ما میگه که جایگاهش تو B کجاست من که نشون دادم امکان داره هر جای آرایه قرار بگیره بازم ج اشتباه میشه و با چه فلسفه ای ما بدونیم [tex]A[i][/tex] حتما کاندید هست واسه جستجو درون آرایه B اگر بخواهیم تکلیف همه‌ی [tex]A[i][/tex] رو بدونیم هزینه [tex]O(n/2*logn)[/tex] میشه که برابر با [tex]O(nlogn)[/tex] که حتی از [tex]O(n)[/tex] بیشتر میشه! ") تا به k امین عنصر برسیم! دوم اینکه الگوریتمی که شما گفتید ۱ بار بر روی a و یک بار بر روی b جستجوی دودویی انجام دادید ( به صورت جدا از هم ... جداگانه) که هزینه‌ها با هم ضرب نمیشن بلکه جمع میشن [tex]O(log n)[/tex] + [tex]O(log n)[/tex] = [tex]O(log n)[/tex]

دوباره یه نگاه به عکس بنداز خودت حرفی رو که زدی رو این شکل انجام بده, اصلا با چی میخوای مقایسه کنی جستجوی دودویی رو گرچه لیست مرتب هست و یه راست میتونی بری سر اغ اندیس ولی ۲ تا آرایه شده بحث فرق داره. ببینم به سومین عنصر میرسی با این روشی که گفتی.... بازم من میگم شاید الگوریتمی با [tex]O(log n)[/tex] این پیدا بشه که من نمیدونم اما روش شما اشتباه هست.

من گفته های شما رو چک کردم و مو به مو انجام دادم . خوشحال میشم یکی از دوستان ج صحیح رو بده
لطفا این کارایی رو که گفتم حتما انجام بدین و چک کنین


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

یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

www پاسخ داده:

مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

قبلا در قسمت طراحی الگوریتمباتوضیچش در فایل گذاشتمبرین ببینینجواب این سوال تغییر نمیکنه در ضمن اینم بگم تو الگوریتم بهترین زمان را باید حساب کنیم حرفای شما با یه الگوریتم هایی که میگین درسته ولی بهترین نیستندواسه همین تو جلد دوم کتاب مقدمه ای بر الگوریتم کورمن مترجم جعفر نژاد قمی دقیقا اینو یه نکته نوشته.

۰
ارسال:
  

Ebramjax پاسخ داده:

مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

دوستان دقیقا یادمه که یافتن کلید میانه در این شرایط با log n به دست میومد که میانه خودش یه کلید k‌ام هست!

۰
ارسال: #۱۰
  

poopi پاسخ داده:

RE: مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

حمیدجان وقتی پستت رو خوندم کلی خندیدم چون به نظر میرسه که اصلا صحبت هام برات مفهوم نبوده و جالب‌تر اینکه منم صحبت های شما رو خوب متوجه نمیشم. حالا ۲ راه داریم
۱) کلا بیخیال شیم چون بنظر میرسه زبون هم رو خوب نمی فهمیم (اصلا با این روش موافق نیستم)
۲) ریز ریز باهم جلو بریم تا ذهن هامون به هم نزدیک بشه
برای شروع بذار اول سر آرایه‌ی C به توافق برسیم.
یه آرایه‌ی Final در نظر بگیر به اینصورت که A و B رو ادغام می کنیم و بعد مرتب میکنیم. از این به بعد در جاهایی که لازم داشتیم از این اسم استفاده می کنیم( این همون برداشت اول شما از آرایه‌ی C هستش که اشتباه بود: rolleyes Smile
و اما C، یه آرایه به اندازه‌ی آرایه‌ی A در نظر بگیر. این آرایه رو به اینصورت میسازیم. برای ساختن [tex]C[i][/tex] میریم توی آرایه‌ی A و [tex]A[i][/tex] رو می بینیم چه عددی هستش. فرض کن عدد a هست. بعد میریم توی Final میبینیم a چندمین عنصر هستش. فرض کن rامین عنصره بعد قرار میدیم [tex]C[i]=r[/tex] مثلا توی همین شکلی که فرستادی فرض کن آرایه‌ی پایینی A هست. بعد می خوایم [tex]C[2][/tex] رو حساب کنیم. داریم [tex]A[2] = 1390[/tex] حالا آرایه‌ی Final رو برای این مثال در نظر بگیر بعد توی اون آرایه ۱۳۹۰ میشه ۵امین عنصر پس قرار میدیم [tex]C[2] = 5[/tex].
*این آرایه ای که میسازیم میشه همون اعدادی که خود شما زیر آرایه نوشتی Big Grin

اگه تا اینجا رو متوجه شدی بقیه رو بخون اگه نه که سر همون قسمت قبلی صحبت کنیم
حالا چه جوری میشه بدون ساختن آرایه‌ی Final آرایه‌ی C رو ساخت؟ گفتیم [tex]C[i]=r[/tex] یعنی اینکه [tex]A[i][/tex]، rامین عنصر در آرایه‌ی Final هست. خوب این معادل اینه که بگیم [tex]A[i][/tex] از r-1 تا از اعداد موجود در ۲ آرایه‌ی A و B بزرگتره.
حالا چه جوری میشه این مقدار رو حساب کرد؟ برای A که [tex]A[i][/tex] دقیقا از i-1 عنصر بزرگتره و برای B هم که این مقدار رو با یک BS می فهمیم، و نهایتا دوتا عدد رو با هم جمع می کنیم و میشه تعداد اعدادی که [tex]A[i][/tex] از اونها بزرگتره فرض کن میشه x وخب داریم که x = r - 1 پس C[i] = x + 1 مفهوم بود؟
پس میشه هر عنصر از C رو با [tex]O(logn)[/tex] ساخت.

۰
ارسال: #۱۱
  

hamidj پاسخ داده:

مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

خدا خیرت بده همون اول اینجوری توضیح میدادی .
تا اونجایی که گفتی متوجه شدم

اما یه سوال واسه ساختنه C مگه نباید از تک تک عناصر A استفاده کرد و در B چک کرد ؟

ارسال: #۱۲
  

poopi پاسخ داده:

RE: مشکل اساسی در سوال ۳۳ الگوریتم( اعتراض)

ببخشید یکم دیر شد Big Grin

(۱۵ اسفند ۱۳۸۹ ۰۱:۲۱ ق.ظ)hamidj نوشته شده توسط:  خدا خیرت بده همون اول اینجوری توضیح میدادی .
تا اونجایی که گفتی متوجه شدم

اما یه سوال واسه ساختنه C مگه نباید از تک تک عناصر A استفاده کرد و در B چک کرد ؟
اگه بخوای کل آرایه رو بسازی آره باید از کل A استفاده کنی و میشه از [tex]O(nlogn)[/tex] ولی طبق توضیحاتی که خواهم داد میبینی که لازم نیست کل C رو بسازیم.

ادامه‌ی مطلب:
گفتیم اگه C[i] = r باشه یعنی اینکه [tex]A[i][/tex]، rامین عنصر در آرایه‌ی Final هست. پس وقتی که دنبال kامین عنصر از آرایه‌ی Final می گردیم معادل اینه که می خواهیم C[i] = k رو پیدا کنیم. یعنی یک i پیدا کنیم که به ازای اون C[i] = k باشه و در این صورت [tex]A[i][/tex] همون kامین عنصر در آرایه‌ی Final هست.
*توجه داشته باشین که ما می خوایم بدون ساختن آرایه‌ی Final این عنصر رو پیدا کنیم چون برای ساختن آرایه‌ی Final پیچیدگی زمانی از [tex]O(n)[/tex] لازمه که برای راه حل ما پیچیدگی زیادیه.
خب حالا می دونیم که آرایه‌ی C صعودیه و ما می خوایم یه i پیدا کنیم که C[i] = k و k هم که در مسئله داده شده این دقیقا معادل همون جستجوی دودویی هست. و با یه جستجوی دودویی می تونیم ایندکس مناسب و در نتیجه جواب مسئله رو پیدا کنیم.
*اگه در جستجوی دودویی هیچ C[i] = k پیدا نشد یعنی kامین عنصر در A نبوده و یک بار همه‌ی مراحل رو برای B تکرار می کنیم.

اگه تا اینجا رو متوجه شدین میریم سراغ قسمت آخر:
پیچیدگی زمانی:
میدونیم که برای جستجوی دودویی در آرایه‌ی C باید حدودا logn خونه از C رو بررسی یا همون [tex]O(logn)[/tex]، اگه به یک خونه از آرایه‌ی C در جستجو سر نزنیم. (می دونیم که خیلی از خونه‌ها اینطوری هستن. یعنی تو BS اصلا سراغشون نمیریم) اصلا نیازی نیست که اون خونه رو بسازیم چون هیچ جای دیگه هم بهش نیاز نداریم. پس به جای اینکه اول آرایه‌ی C رو بطور کامل بسازیم و بعد از BS استفاده کنیم. شروع می کنیم و جستجوی دودویی رو انجام میدیم و به هر خونه از C که رسیدیم ابتدا مقدارش رو حساب می کنیم و بعد، از اون مقدار برای ادامه‌ی جستجو استفاده می کنیم.
همونطور که گفتیم ساختن یه خونه از آرایه‌ی C از [tex]O(logn)[/tex] هستش و چون در BS تعداد خونه هایی که بررسی میشن از [tex]O(logn)[/tex] هستن پس در کل پیچیدگی زمانی الگوریتم از [tex]O(log^{2}n)[/tex] هستش.
تمام Smile
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل و بررسی سوالات مدارمنطقی دکتری ۹۲ گرایش معماری nomad:D ۲۵ ۲۳,۹۳۸ ۲۰ بهمن ۱۴۰۲ ۱۰:۳۸ ق.ظ
آخرین ارسال: masoumeh97
  بررسی سوالات تخصصی دکتری هوش masoomeh_s ۱ ۱,۹۳۰ ۰۱ اسفند ۱۴۰۰ ۰۱:۰۹ ب.ظ
آخرین ارسال: vejdani
  آزمون دکتری نرم افزار و الگوریتم ۱۴۰۰ Seyyedab ۴۶ ۱۷,۸۵۶ ۰۹ مهر ۱۴۰۰ ۰۵:۳۷ ب.ظ
آخرین ارسال: Seyyedab
  بررسی اعتبار یک مجله برای چاپ مقاله one hacker alone ۰ ۱,۹۷۴ ۲۱ اردیبهشت ۱۴۰۰ ۱۲:۲۶ ق.ظ
آخرین ارسال: one hacker alone
  تشریح تست همروندی - بررسی یکی از سوالات سال ۸۲ abji22 ۵ ۴,۶۲۷ ۰۲ دى ۱۳۹۹ ۱۱:۰۵ ق.ظ
آخرین ارسال: mohammadasadi1
  بررسی سوالات دکتری isoa ۲ ۲,۶۲۳ ۰۸ آبان ۱۳۹۹ ۰۸:۳۴ ب.ظ
آخرین ارسال: RoghayehAlipanahi
  آزمون دکتری نرم افزار و الگوریتم ۹۹ Seyyedab ۱۱ ۵,۷۰۴ ۰۲ شهریور ۱۳۹۹ ۱۱:۰۳ ق.ظ
آخرین ارسال: Seyyedab
  بررسی وضعیت کار و درآمد گرایشهای مختلف. عزیز دادخواه ۱ ۲,۴۲۸ ۰۴ دى ۱۳۹۸ ۰۱:۱۲ ب.ظ
آخرین ارسال: marvelous
  بحث و بررسی پیرامون بیگ بنگ و شکل گیری حیات marvelous ۳ ۵۹ ۰۱ آذر ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: marvelous
  حریدار فیلم آموزشی دروس برای کنکور نرم افزار NersiA ۱ ۲,۲۷۲ ۱۷ شهریور ۱۳۹۸ ۱۱:۴۷ ق.ظ
آخرین ارسال: nazanin2020

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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