سوال اول و دوم از کتاب پوران فصل ۲(تقسیم و غلبه)
۱) در الگوریتم 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]
اینو تو CLRS یافتم یکم شبیش بود:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
اینم یکی دیگه :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
شاید کمکت کنه
فعلا وقت نکردم بیشتر از این
اگه تونستم بیشتر حل می کنم
اگه حلشو یاد گرفتید به منم بگید
تا اینجا برات حل کردم :
[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]\frac{(4 3k)n}{4k} k 1\leqslant \frac{-an}c{}[/tex]
(۲۷ آذر ۱۳۹۱ ۰۶:۰۷ ق.ظ)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 کوچکتر از ۴ گفته بود غیر خطی میشه
چرا؟؟؟
در مورد قضیه ی 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 کمتر باشه.
(۲۵ آذر ۱۳۹۱ ۰۶:۲۲ ب.ظ)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) حداقل " نوشتید رو می گم . کلا میشه تحلیل بدست اوردن این فرمول رو بگین ؟؟
(۰۱ دى ۱۳۹۱ ۰۳:۱۱ ب.ظ)nazaninzahra2 نوشته شده توسط: شاید بپرسی اون دو از کجا اومده ؟ اون دو که توی فرمول هست از این مسئله اومده که اون دسته کمتر از k عنصر و اون دسته ایی که خود میانه میانه داخلش هست رو حساب نکردیم. (همون دو که منها کردم منظورمه)
ببخشید که بد توضیح دادم.
عالی گفتی عالی
مرسی یه دنیا ممنون .
فقط یه سوال دیگه
ایمجا این شکل رو ببین مال الگوریتم دوم انتخاب وقتی ازایه رو به ۵ قسمت تقسیم می کنیم .
این ۴ قسمت رو از چپ توضیح می دم . اخری رو نمی دونم برای چی ؟
اولی از چپ : تعداد نصف میانه ها
دومی از چپ : در هر بسته ۵ تایی ۲ تا بزر گتر از میانه هست .پس ضربدر ۲ داریم
سومی : به همون دلیل که خودت گفتی .
چهارمی چرا ؟؟؟؟؟؟؟؟؟
(۰۱ دى ۱۳۹۱ ۱۱:۲۰ ب.ظ)ana_12345 نوشته شده توسط:سلام یکم گنگ نوشتی، متوجه نمیشم ! واضح تر بگو ! این عکس رو از کجا آوردی ؟ اولی از سمت چپ چرا منهای یک داره ؟(01 دى ۱۳۹۱ ۰۳:۱۱ ب.ظ)nazaninzahra2 نوشته شده توسط: شاید بپرسی اون دو از کجا اومده ؟ اون دو که توی فرمول هست از این مسئله اومده که اون دسته کمتر از k عنصر و اون دسته ایی که خود میانه میانه داخلش هست رو حساب نکردیم. (همون دو که منها کردم منظورمه)
ببخشید که بد توضیح دادم.
عالی گفتی عالی
مرسی یه دنیا ممنون .
فقط یه سوال دیگه
ایمجا این شکل رو ببین مال الگوریتم دوم انتخاب وقتی ازایه رو به ۵ قسمت تقسیم می کنیم .
این ۴ قسمت رو از چپ توضیح می دم . اخری رو نمی دونم برای چی ؟
اولی از چپ : تعداد نصف میانه ها
دومی از چپ : در هر بسته ۵ تایی ۲ تا بزر گتر از میانه هست .پس ضربدر ۲ داریم
سومی : به همون دلیل که خودت گفتی .
چهارمی چرا ؟؟؟؟؟؟؟؟؟
صورت سوال چیه ؟
(فقط یه چیز میفهمم اونم اینه که وقتی به دسته های ۵ تایی داری تقسیم میکنی و n ضریب پنج هست دیگه دسته ایی کمتر از ۵ وجود نداره و همه دسته ها ۵ تا عنصر دارن)
(۲۵ آذر ۱۳۹۱ ۰۶:۲۲ ب.ظ)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]
جرا به جای ۲k-1 میذاریم ۳ ؟