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


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

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

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

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

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

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

این استدلال که میگید می تونه تو همه‌ی خونه‌ها باشه پس باید همه‌ی خونه‌ها مقایسه بشه درست نیست، پس الگوریتم BinarySearch به چه دردی می خوره؟
مثال مشابه اینه که یه آرایه‌ی مرتب با 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] رو خواستید بگید خلاصه بنویسم

(۱۲ اسفند ۱۳۸۹ ۰۳:۳۳ ق.ظ)poopi نوشته شده توسط:  این استدلال که میگید می تونه تو همه‌ی خونه‌ها باشه پس باید همه‌ی خونه‌ها مقایسه بشه درست نیست، پس الگوریتم BinarySearch به چه دردی می خوره؟
مثال مشابه اینه که یه آرایه‌ی مرتب با 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] این پیدا بشه که من نمیدونم اما روش شما اشتباه هست.

---

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

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

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

حمیدجان وقتی پستت رو خوندم کلی خندیدم چون به نظر میرسه که اصلا صحبت هام برات مفهوم نبوده و جالب‌تر اینکه منم صحبت های شما رو خوب متوجه نمیشم. حالا ۲ راه داریم
۱) کلا بیخیال شیم چون بنظر میرسه زبون هم رو خوب نمی فهمیم (اصلا با این روش موافق نیستم)
۲) ریز ریز باهم جلو بریم تا ذهن هامون به هم نزدیک بشه
برای شروع بذار اول سر آرایه‌ی C به توافق برسیم.
یه آرایه‌ی Final در نظر بگیر به اینصورت که A و B رو ادغام می کنیم و بعد مرتب میکنیم. از این به بعد در جاهایی که لازم داشتیم از این اسم استفاده می کنیم( این همون برداشت اول شما از آرایه‌ی C هستش که اشتباه بود: rolleyes
و اما 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].
*این آرایه ای که میسازیم میشه همون اعدادی که خود شما زیر آرایه نوشتی

اگه تا اینجا رو متوجه شدی بقیه رو بخون اگه نه که سر همون قسمت قبلی صحبت کنیم
حالا چه جوری میشه بدون ساختن آرایه‌ی 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] ساخت.

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

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

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

(۱۵ اسفند ۱۳۸۹ ۰۱:۲۱ ق.ظ)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] هستش.
تمام