۰
subtitle
ارسال: #۱
چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
سوال اول و دوم از کتاب پوران فصل ۲(تقسیم و غلبه)
۱) در الگوریتم selection (همان الگوریتم بهینه برای یافتن k امین کوچکترین عنصر در آرایه n تایی به کمک میانه میانه ها)آرایه ورودی به گروه های ۵ تایی تقسیم شدند آیا اگر به گروه های ۷ عنصری تقسیم کنیم زمان همچنان خطی است؟ به گروه های ۳ عنصری چطور؟
پاسخ:
فرض کنیم گروه ها k عنصری باشند تعداد اعداد بزرگتر( یا کوچکتر) از میانه میانه ها(x) حداقل
[tex]\left \lceil \frac{k}{2} \right \rceil \left ( \left \lceil \frac{1}{2} \left \lceil \frac{n}{k} \right \rceil\right \rceil -2\right )\geq \frac{n}{4}- k[/tex]
است، پس در بدترین حالت selection به صورت بازگشتی روی حداکثر
[tex]n -\left ( \frac{n}{4} - k\right )= \frac{3n}{4} k[/tex]
عنصر اجرا میشود.
[tex]T(n)\leq T\left ( \left \lceil \frac{n}{k} \right \rceil \right ) T\left ( \frac{3n}{4} k\right ) O\left ( n \right )[/tex]
تا این جا رو مشکلی ندارم
سوالم از اینجا به بعده :
برای آنکه این رابطه خطی باشد باید [tex]T\left ( n \right )\leq cn[/tex] که با جایگذاری ثابت میشود :
[tex]k> 4[/tex]
عدد چطور بدست اومده؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
تو رابطه میذارم
اما ۴ بدست نمیاد
۲)نشان دهید اگر [tex]n\geq 140[/tex] حداقل [tex]\left \lceil \frac{n}{4} \right \rceil[/tex] عنصر از n بزرگتر و حداقل [tex]\left \lceil \frac{n}{4} \right \rceil[/tex] عنصر از n کوچکتر است؟
۳) اگر در الگوریتم selection به دسته های ۲k-1 عنصری تقسیم کنیم رابطه T(n) به صورت زیر بدست می آید:
[tex]T(n)=\theta\left ( n \right ) T\left ( \left \lceil \frac{n}{2k-1} \right \rceil \right ) T\left ( \frac{3k-2}{2(2k-1))}n 2k \right )[/tex]
T دوم رو متوجه نمیشم.
۴)حداکثر تعداد عناصری که میتوانند در دو طرف میانه میانه ها باشد؟
[tex]2\left ( \frac{n}{5} \right )-1[/tex]
۱) در الگوریتم selection (همان الگوریتم بهینه برای یافتن k امین کوچکترین عنصر در آرایه n تایی به کمک میانه میانه ها)آرایه ورودی به گروه های ۵ تایی تقسیم شدند آیا اگر به گروه های ۷ عنصری تقسیم کنیم زمان همچنان خطی است؟ به گروه های ۳ عنصری چطور؟
پاسخ:
فرض کنیم گروه ها k عنصری باشند تعداد اعداد بزرگتر( یا کوچکتر) از میانه میانه ها(x) حداقل
[tex]\left \lceil \frac{k}{2} \right \rceil \left ( \left \lceil \frac{1}{2} \left \lceil \frac{n}{k} \right \rceil\right \rceil -2\right )\geq \frac{n}{4}- k[/tex]
است، پس در بدترین حالت selection به صورت بازگشتی روی حداکثر
[tex]n -\left ( \frac{n}{4} - k\right )= \frac{3n}{4} k[/tex]
عنصر اجرا میشود.
[tex]T(n)\leq T\left ( \left \lceil \frac{n}{k} \right \rceil \right ) T\left ( \frac{3n}{4} k\right ) O\left ( n \right )[/tex]
تا این جا رو مشکلی ندارم
سوالم از اینجا به بعده :
برای آنکه این رابطه خطی باشد باید [tex]T\left ( n \right )\leq cn[/tex] که با جایگذاری ثابت میشود :
[tex]k> 4[/tex]
عدد چطور بدست اومده؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
تو رابطه میذارم
اما ۴ بدست نمیاد
۲)نشان دهید اگر [tex]n\geq 140[/tex] حداقل [tex]\left \lceil \frac{n}{4} \right \rceil[/tex] عنصر از n بزرگتر و حداقل [tex]\left \lceil \frac{n}{4} \right \rceil[/tex] عنصر از n کوچکتر است؟
۳) اگر در الگوریتم selection به دسته های ۲k-1 عنصری تقسیم کنیم رابطه T(n) به صورت زیر بدست می آید:
[tex]T(n)=\theta\left ( n \right ) T\left ( \left \lceil \frac{n}{2k-1} \right \rceil \right ) T\left ( \frac{3k-2}{2(2k-1))}n 2k \right )[/tex]
T دوم رو متوجه نمیشم.
۴)حداکثر تعداد عناصری که میتوانند در دو طرف میانه میانه ها باشد؟
[tex]2\left ( \frac{n}{5} \right )-1[/tex]
۰
ارسال: #۲
چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
اینو تو CLRS یافتم یکم شبیش بود:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اینم یکی دیگه :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
شاید کمکت کنه
فعلا وقت نکردم بیشتر از این
اگه تونستم بیشتر حل می کنم
اگه حلشو یاد گرفتید به منم بگید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اینم یکی دیگه :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
شاید کمکت کنه
فعلا وقت نکردم بیشتر از این
اگه تونستم بیشتر حل می کنم
اگه حلشو یاد گرفتید به منم بگید
۰
ارسال: #۳
چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
تا اینجا برات حل کردم :
[tex]T(n)\leqslant T(\left \lceil \frac{n}{k} \right \rceil) T(\frac{3n}{4} k) \Theta (n) \leqslant cn/k c 3cn/4 ck an=\frac{(4 3k)cn}{4k} (k 1)c an= cn (-\frac{k-4}{4k}cn (k 1)c an)\leqslant cn\Rightarrow \frac{4-k}{4k}cn (k 1)c an\leqslant0\Rightarrow [/tex]
امیدوارم قسمت آخر رو دیگه خودت حل کنی به منم یاد بدی
[tex]T(n)\leqslant T(\left \lceil \frac{n}{k} \right \rceil) T(\frac{3n}{4} k) \Theta (n) \leqslant cn/k c 3cn/4 ck an=\frac{(4 3k)cn}{4k} (k 1)c an= cn (-\frac{k-4}{4k}cn (k 1)c an)\leqslant cn\Rightarrow \frac{4-k}{4k}cn (k 1)c an\leqslant0\Rightarrow [/tex]
امیدوارم قسمت آخر رو دیگه خودت حل کنی به منم یاد بدی
ارسال: #۴
RE: چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
(۲۷ آذر ۱۳۹۱ ۰۶:۰۷ ق.ظ)csharpisatechnology نوشته شده توسط: تا اینجا برات حل کردم :
[tex]T(n)\leqslant T(\left \lceil \frac{n}{k} \right \rceil) T(\frac{3n}{4} k) \Theta (n) \leqslant cn/k c 3cn/4 ck an=\frac{(4 3k)cn}{4k} (k 1)c an= cn (-\frac{k-4}{4k}cn (k 1)c an)\leqslant cn\Rightarrow \frac{4-k}{4k}cn (k 1)c an\leqslant0\Rightarrow [/tex]
برای اینکه این عبارت کمتر مساوی ۰ باشه با فرض a<c که البته اگه در نظر هم نگیریم فرقی نمیکنه باید ضریب cn از ۰ کوچکتر باشه که بدست میاد k>4
که مرتبه خطی میشه
برای k کوچکتر از ۴ گفته بود غیر خطی میشه
چرا؟؟؟
۰
ارسال: #۵
چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
اینم معادل جوابه:
[tex]\frac{(4 3k)n}{4k} k 1\leqslant \frac{-an}c{}[/tex]
[tex]\frac{(4 3k)n}{4k} k 1\leqslant \frac{-an}c{}[/tex]
۰
ارسال: #۶
چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
در مورد قضیه ی Master(اصلی)،بهترین روش یادگیری رو توی جزوه های دستنویس هادی یوسفی دیدم و سعی کردم خلاصشو فرموله کنم بذارم اینجا
[tex]T(n)=A F(n),A=aT(n/b)[/tex]
[tex]if \Theta(A)>\Theta(F(n))\Rightarrow T(n)=\Theta(A)[/tex]
[tex]if \Theta(F(n))>\Theta(A)\Rightarrow T(n)=\Theta(F(n))[/tex]
![[تصویر: 149463_1_1379087161.gif]](https://img.manesht.ir/149463_1_1379087161.gif)
[tex]\LARGE \Theta(A)=n^{Log_{b}a}[/tex]
البته موارد استثنا هم وجود داره که توی جای مختلف باید از روش های درخت بازگشت و روش های تبدیل متغیر یا روش های دیگه و استقراء و برهان خلف و غیره حلش کنیم.
در اینجا F(n ما همون Cn هست
پس A باید از Cn کمتر باشه تا همون ((Teta(F(n رو قبول کنیم
( Teta(f(n))=teta(cn
پس تتای A باید از Cn کمتر باشه.
[tex]T(n)=A F(n),A=aT(n/b)[/tex]
[tex]if \Theta(A)>\Theta(F(n))\Rightarrow T(n)=\Theta(A)[/tex]
[tex]if \Theta(F(n))>\Theta(A)\Rightarrow T(n)=\Theta(F(n))[/tex]
[tex]\LARGE \Theta(A)=n^{Log_{b}a}[/tex]
البته موارد استثنا هم وجود داره که توی جای مختلف باید از روش های درخت بازگشت و روش های تبدیل متغیر یا روش های دیگه و استقراء و برهان خلف و غیره حلش کنیم.
در اینجا F(n ما همون Cn هست
پس A باید از Cn کمتر باشه تا همون ((Teta(F(n رو قبول کنیم
( Teta(f(n))=teta(cn
پس تتای A باید از Cn کمتر باشه.
۰
ارسال: #۷
RE: چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
(۲۵ آذر ۱۳۹۱ ۰۶:۲۲ ب.ظ)reyhaneh64 نوشته شده توسط: سوال اول و دوم از کتاب پوران فصل ۲(تقسیم و غلبه)می شه این قسمت رو که متوجه شدید توضیح بدید ؟؟؟ من این فرمول رو نمی فهمم. چرا ضربدر K/2 ??
۱) در الگوریتم selection (همان الگوریتم بهینه برای یافتن k امین کوچکترین عنصر در آرایه n تایی به کمک میانه میانه ها)آرایه ورودی به گروه های ۵ تایی تقسیم شدند آیا اگر به گروه های ۷ عنصری تقسیم کنیم زمان همچنان خطی است؟ به گروه های ۳ عنصری چطور؟
پاسخ:
فرض کنیم گروه ها k عنصری باشند تعداد اعداد بزرگتر( یا کوچکتر) از میانه میانه ها(x) حداقل
[tex]\left \lceil \frac{k}{2} \right \rceil \left ( \left \lceil \frac{1}{2} \left \lceil \frac{n}{k} \right \rceil\right \rceil -2\right )\geq \frac{n}{4}- k[/tex]
است، پس در بدترین حالت selection به صورت بازگشتی روی حداکثر
[tex]n -\left ( \frac{n}{4} - k\right )= \frac{3n}{4} k[/tex]
عنصر اجرا میشود.
[tex]T(n)\leq T\left ( \left \lceil \frac{n}{k} \right \rceil \right ) T\left ( \frac{3n}{4} k\right ) O\left ( n \right )[/tex]
تا این جا رو مشکلی ندارم
توی فرمول بالا که برای محاسبه " تعداد اعداد بزرگتر( یا کوچکتر) از میانه میانه ها(x) حداقل " نوشتید رو می گم . کلا میشه تحلیل بدست اوردن این فرمول رو بگین ؟؟
۰
ارسال: #۸
RE: چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
(۲۵ آذر ۱۳۹۱ ۰۶:۲۲ ب.ظ)reyhaneh64 نوشته شده توسط: ۳) اگر در الگوریتم selection به دسته های ۲k-1 عنصری تقسیم کنیم رابطه T(n) به صورت زیر بدست می آید:
[tex]T(n)=\theta\left ( n \right ) T\left ( \left \lceil \frac{n}{2k-1} \right \rceil \right ) T\left ( \frac{3k-2}{2(2k-1))}n 2k \right )[/tex]
اثبات جواب این سوال:
زمان لازم برای یافتن میانه [tex]\left ( \left \lceil \frac{n}{2k-1} \right \rceil \right )[/tex] میانه به صورت بازگشتی:
[tex]T\left ( \left \lceil \frac{n}{2k-1} \right \rceil \right )[/tex]
هزینه لازم برای partition کردن دو طرف میانه میانه ها و...
[tex]\theta \left (n \right )[/tex]
حداقل تعداد عناصر بزرگتر(یا کوچکتر از) میانه میانه ها وقتی به دسته های ۲k-1 عنصری تقسیم میکنیم:
[tex]\left ( \frac{1}{2}\left \lceil \frac{n}{2k-1} \right \rceil -2\right )\times \left ( \frac{2k-1-1}{2} 1\right )=\frac{k}{2}\left \lceil \frac{n}{2k-1} \right \rceil-2k \Rightarrow[/tex]
(((((((((((((((توجه: تعداد عناصر بزرگتر از میانه میانه ها در هر دسته:
در هر دسته ۲k-1 عنصره :میانه را کم میکنیم بر ۲ تقسیم میکنیم با ۱(میانه دسته) جمع میکنیم
میشه [tex]( \frac{2k-1-1}{2}) \right )[/tex])))))))))))))))
بعد از نتیجه عبارت بالا محاسبات را انجام داده :
[tex]\left ( \frac{nk}{2(2k-1)} -2k \right)[/tex]
برای یافتن حداکثر تعداد عناصر از n عبارت بالا را کم میکنیم:
[tex]n- \left ( \frac{nk}{2(2k-1)} -2k \right)= n\ \left ( \frac{4k-2-k}{2(2k-1)} \right ) 2k= n\left ( \frac{3k-2}{2(2k-1)}\right ) 2k[/tex]
پس جواب کلی میشه:
[tex]T(n)=\theta\left ( n \right ) T\left ( \left \lceil \frac{n}{2k-1} \right \rceil \right ) T\left ( \frac{3k-2}{2(2k-1))}n 2k \right )[/tex]
(۲۷ آذر ۱۳۹۱ ۰۶:۲۶ ب.ظ)reyhaneh64 نوشته شده توسط:(27 آذر ۱۳۹۱ ۰۶:۰۷ ق.ظ)csharpisatechnology نوشته شده توسط: تا اینجا برات حل کردم :
[tex]T(n)\leqslant T(\left \lceil \frac{n}{k} \right \rceil) T(\frac{3n}{4} k) \Theta (n) \leqslant cn/k c 3cn/4 ck an=\frac{(4 3k)cn}{4k} (k 1)c an= cn (-\frac{k-4}{4k}cn (k 1)c an)\leqslant cn\Rightarrow \frac{4-k}{4k}cn (k 1)c an\leqslant0\Rightarrow [/tex]
برای اینکه این عبارت کمتر مساوی ۰ باشه با فرض a<c که البته اگه در نظر هم نگیریم فرقی نمیکنه باید ضریب cn از ۰ کوچکتر باشه که بدست میاد k>4
که مرتبه خطی میشه
برای k کوچکتر از ۴ گفته بود غیر خطی میشه
چرا؟؟؟
برای غیر خطی بودن مرتبه رابطه به ازای k<4 در رابطه بالا که اثبات شد
به جای ۲k-1 میذاریم ۳
به رابطه زیر میرسیم:
۲k-1=3
k=2
[tex]T(n)=T(\frac{n}{3}) T(\frac{2}{3}n) \theta (n))[/tex]
که میدانیم با درخت بازگشت حلش میشه:
[tex]T(n)=omega(nlog n)[/tex]
۰
ارسال: #۹
چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
جرا به جای ۲k-1 میذاریم ۳ ؟
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close