انجمنصفحه اولجستجوی انجمن

[Masoud05]

این سوال قبلا یه بار بررسی شده اما از اونجایی که تست خوبی هست اون ارسال رو حذف میکنم تا سوالات تکراری نباشه( فقط ارسال خودم رو پاک میکنم و نه مال هیچکس دیگه!) و در ضمن یه بار با کمک هم این سوال قشنگ رو بررسی کنیم‌:

[Masoud05]

خب کسی نظری نداره ؟! - جواب زیر همون جواب قبلی خودمه که دوباره گزاشتمش‌، اگه کسی راه بهتری بلده یا نکته ای میخواهد اضافه کنه‌، مطلبش رو همینجا بزاره.

از آنجایی که آرایه‌ها مرتب هستند پس یافتن میانه هر یک از آرایه‌ها مستقل از تعداد عناصر آرایه در زمان ثابت قابل یافتن است .
برای حل این مسئله تکنیک های زیادی وجود دارد اما با توجه به اینکه:

۱ )اگر مسائل را تقسیم کنیم و هر یک را جدا حل نماییم به جواب میرسیم
۲) حل زیر مسائل بهم وابسته نیست و فقط نتایج را با هم مقایسه میکنیم.

می توان نتیجه گرفت رهیافت تقسیم و غلبه برای حل این مسئله مناسب است.
اما تقسیم و غلبه چگونه این مسئله را حل می کند‌:

راه حل )میانه‌ها را به هم مقایسه کن‌، ۳ حالت رخ می دهد:

۱- میانه‌ها با هم برابرند ----> جواب کل همان میانه آرایه هاست - که البته چون اعداد از هم مجزا هستند این مورد برای این مسئله رخ نمی دهد.
۲- میانه آرایه ۱ از میانه آرایه ۲ بزرگتر است ----> نتیجه میگیریم که جواب در نیمه اول آرایه ۱ و یا نیمه دوم آرایه ۲ است چراکه در آرایه ۱ همانطور که گفته شد میانه این آرایه بزرگتر از مقدار مطلوب است پس باید به دنبال عناصر کوچکتراز میانه آرایه۱ که همان نیمه اول میشود گشت . همینطور هم اثبات میشود که باید دنبال عناصر بزرگتر از میانه در آرایه ۲ گشت که میشود نیمه دوم
۳- معکوس حالت ۲

در واقع با هر مرحله فراخوانی مجدد الگوریتم‌، هر آرایه نصف میشود پس در بدترین حالت باید به جایی برسیم که فقط هر زیر آرایه فقط ۱ عنصر دارد . این دنباله سبب ایجاد پیچیدگی زمانی لگاریتمی می شود:

$T(2n)=T(n/2) T(n/2) O(1)=2T(n/2) O(1) = O(Log n)$

توجه داشته باشید که تعداد کل عناصر ۲n هست و زمان (O(1 جهت تقسیم و یک مقایسه ساده است و ما به دنبال (T(2n هستیم.

یعنی گزینه ۱ صحیح است.

[atharrashno]

در مورد جواب اخر این سوال که نهایتا به لگاریتم میرسیم یه خورده توضیح بدین با تغییر متغیر به رادیکال ۲nمیرسیم و میدونیم رشد رادیکال بیشتر لگاریتم هست!

[Masoud05]

فرض کنید ‌: m =2n پس n/2= m/4 با توجه به ‌:

$T(2n)=T(n/2) T(n/2) O(1)= 2T(n/2) O(1)=O(Log n)$

در نتیجه خواهیم داشت‌:


$T(m)=T(m/4) T(m/4) O(1) = 2T(m/4) O(1) = O(Log m) = O(Log n)$

[atharrashno]

بله اونو متوجه بودم اما در همین جا که m متغیر ما است جه طور
۲T(m/4)+O(1)0=O(Logm)

اگر از قضیه اصلی استفاده کنیم که میشه لگاریتم ام

[Masoud05]

(۱۸ بهمن ۱۳۹۰ ۱۱:۳۵ ق.ظ)atharrashno نوشته شده توسط:  بله اونو متوجه بودم اما در همین جا که m متغیر ما است جه طور
۲T(m/4)+O(1)0=O(Logm)

اگر از قضیه اصلی استفاده کنیم که میشه لگاریتم ام

خب کافیه m رو به n تبدیل کنی تا جواب مورد نظر بدست بیاد!

[atharrashno]

where is my wro

ng?

[Aurora]

فکر کنم اگه این طوری بگیم بهتره:

$t(2n)=t(2n/2) 1\Rightarrow t(2n)=t(n) 1\Rightarrow t(m)=t(m/2) 1\Rightarrow t(m)=o(logm)\Rightarrow t(n)=o(logn)$

[Masoud05]

(۲۰ بهمن ۱۳۹۰ ۰۱:۰۱ ب.ظ)saeedeh123 نوشته شده توسط:  فکر کنم اگه این طوری بگیم بهتره:

$t(2n)=t(2n/2) 1\Rightarrow t(2n)=t(n) 1\Rightarrow t(m)=t(m/2) 1\Rightarrow t(m)=o(logm)\Rightarrow t(n)=o(logn)$

روش صحیحیش هم همینه . منم بالا در اولین ارسال همین رو نوشتم اما با تغییر متغیر هم میشه حلش کرد . تنها ابهامی که هست اینه که تعداد داده‌ها ۲n هست و همین باعث میشه این رابطه کمی گنگ به نظر بیاد در حالی که مسئله ساده ای هست .

[atharrashno]

دوستان من بلا خره این طوری این قضیه را برا خودم هضم کردم:
تعداد عناصر بعد از هر مقایسه
$2n-\frac{n}{2}-\frac{n}{2}=n$

پس $T(2n)=T(n) O(1)$
حالا m=n
$T(m)=T(\frac{m}{2}) O(1)$
,
اشتباه من این بود که اصولا نوشتن این جمله اشتباه است:
$T(2n)=T(\frac{n}{2}) T(\frac{n}{2}) O(1)$
چراکه $T(2n)$ ارایه ای است نامرتب اما $T(\frac{n}{2})$ در مورد $n$ صحبت میکند که عناصر ان مرتب است

[Masoud05]

(۲۱ بهمن ۱۳۹۰ ۰۸:۵۵ ب.ظ)atharrashno نوشته شده توسط:  اشتباه من این بود که اصولا نوشتن این جمله اشتباه است:
$T(2n)=T(\frac{n}{2}) T(\frac{n}{2}) O(1)$

چرا این غلطه ؟ بنظرم که درسته!

[atharrashno]

این جمله غلطه چون:
۱ شما با این رابطه ای که از معادله بازگشتی بالا بدست میاد نمیتونید به لگاریتم برسید
۲ دلیل اصلی این قصه اینه که t(n/2نمونه کوچک شده ای از t(2nنیست شما میانه را در t(n/2 با درجه یک بدست می اورید چون از خاصیت مرتب بودن اعضا در n عنصر استفاده کرده‌اید اما در t(2nاثبات میشود که پیدا کردن میانه از درجه logn است
مساله ما به دو زیر مساله تقسم نمیشود اما اعضای ما در هرمقایسه نصف میشود

۳ با ادرس مقسمی حل کامل این الگوریتم درصحفه۷۵ کتاب design and analysis of parallel algorithm manual solutionموجود است چون تمامی لینک‌ها برای من ف‌ی ل ت ر بود به پاسخ دست پیدا نکردم اگر شما دارید دانلود کنید و تصویر پاسخ را برای ما به اشتراک بگزارید

[پشتکار]

بچه‌ها روش حل من چطوره؟
ضمنا این سوال هوشه نه نرم افزار، درسته؟
$t(2n)=t(\frac{n}{2}) t(\frac{n}{2}) O(1)$
با تغییر متغیر m=2n داریم:
$t(m)=t(\frac{m}{4}) t(\frac{m}{4}) O(1)$
که برابر است با:
$t(m)=2t(\frac{m}{4}) O(1)$
و داریم:
$g(m)=m^{log_{4}^{2}}=m^{\frac{1}{log_{2}^{4}}}=\sqrt{m}$
حالا بجای m مقدار ۲n رو قرار می دهیم و داریم:
$\sqrt{m}=\sqrt{2n}\in O(\sqrt{n})$

کجا دارم اشتباه می کنم؟

[Aurora]

(۲۳ بهمن ۱۳۹۰ ۱۲:۲۶ ق.ظ)atharrashno نوشته شده توسط:  این جمله غلطه چون:
۱ شما با این رابطه ای که از معادله بازگشتی بالا بدست میاد نمیتونید به لگاریتم برسید
۲ دلیل اصلی این قصه اینه که t(n/2نمونه کوچک شده ای از t(2nنیست شما میانه را در t(n/2 با درجه یک بدست می اورید چون از خاصیت مرتب بودن اعضا در n عنصر استفاده کرده‌اید اما در t(2nاثبات میشود که پیدا کردن میانه از درجه logn است
مساله ما به دو زیر مساله تقسم نمیشود اما اعضای ما در هرمقایسه نصف میشود

۳ با ادرس مقسمی حل کامل این الگوریتم درصحفه۷۵ کتاب design and analysis of parallel algorithm manual solutionموجود است چون تمامی لینک‌ها برای من ف‌ی ل ت ر بود به پاسخ دست پیدا نکردم اگر شما دارید دانلود کنید و تصویر پاسخ را برای ما به اشتراک بگزارید

من این کتابو پیدا کردم نمی دونم همون کتابی که شما نوشتید هست یانه ولی صفحه ۷۴ و ۷۵ درباره همین سوال توضیح داده.

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

---

(۲۳ بهمن ۱۳۹۰ ۰۲:۰۶ ق.ظ)پشتکار نوشته شده توسط:  بچه‌ها روش حل من چطوره؟
ضمنا این سوال هوشه نه نرم افزار، درسته؟
$t(2n)=t(\frac{n}{2}) t(\frac{n}{2}) O(1)$
با تغییر متغیر m=2n داریم:
$t(m)=t(\frac{m}{4}) t(\frac{m}{4}) O(1)$
که برابر است با:
$t(m)=2t(\frac{m}{4}) O(1)$
و داریم:
$g(m)=m^{log_{4}^{2}}=m^{\frac{1}{log_{2}^{4}}}=\sqrt{m}$
حالا بجای m مقدار ۲n رو قرار می دهیم و داریم:
$\sqrt{m}=\sqrt{2n}\in O(\sqrt{n})$

کجا دارم اشتباه می کنم؟

شما با توجه به رابطه اولی که نوشتید یعنی$t(2n)=t(\frac{n}{2}) t(\frac{n}{2}) O(1)$ ادامه جواب را درست حل کردید ولی
احتمالا چون دوتا رابطه باید باهم حل بشند یعنی اینکه به هم وابسته هستند باید به صورت
$t(2n)=t(n) O(1)$ نه اینکه هر کدام را جدا بنویسیم.

[Aurora]

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