مرتبه
[tex]T(n) = T(\frac{n}{2}) T(\frac{n}{3}) \Theta(n)[/tex]
البته تو صورت سوال نوشته شده حد پایین n/2 و حد بالای n/3.
بنده سعی کردم که با روش رسم درخت بازگشتی حلش کنم. ارتفاع درخت رو برابر طولانیترین مسیر گرفتم.(n/2).پیچیدگی هر سطح درخت هم گرفتم n و ارتفاع * اندازه هر سطح بدست آوردم nlogn که البته اشتباهه و پاسخ صحیح O(n) هستش.
پیغام admin: بابا TeX نوشتن سخت نیست. این ابزاری که ما توی سایت گذاشتیم کار باهاش خیلی راحته. خودم TeX رو به مطلبتون اضافه کردم که ببینید چقدر راحت و آسون و خوانا است.
با توجه به اینکه توی صورت سوال نوشته حد پایین n/2 و حد بالای n/3 پس نتیجه میگیریم:
[tex]T(\frac{n}2)\leq T(\frac{n}3)[/tex]
پس:
[tex]T(\frac{n}2) T(\frac{n}3) \Theta (n)\leq 2T(\frac{n}3) \Theta (n)[/tex]
طبق قضیه اساسی:
[tex]T(n)=O(n)[/tex]
(۲۹ دى ۱۳۸۹ ۰۲:۳۲ ق.ظ)حامد نوشته شده توسط: با توجه به اینکه توی صورت سوال نوشته حد پایین n/2 و حد بالای n/3 پس نتیجه میگیریم:اینو چه جوری نتیجه گرفتین؟
[tex]T(\frac{n}2)\leq T(\frac{n}3)[/tex]
صورت سوال دقیقا چی گفته در این مورد.
(۲۸ دى ۱۳۸۹ ۱۲:۵۳ ب.ظ)sos006 نوشته شده توسط: پیغام admin: بابا TeX نوشتن سخت نیست. این ابزاری که ما توی سایت گذاشتیم کار باهاش خیلی راحته. خودم TeX رو به مطلبتون اضافه کردم که ببینید چقدر راحت و آسون و خوانا است.
دم شما گرم.
من بعد به روی دو دیده
(۲۹ دى ۱۳۸۹ ۱۱:۱۳ ب.ظ)sepid نوشته شده توسط:(29 دى ۱۳۸۹ ۰۲:۳۲ ق.ظ)حامد نوشته شده توسط: با توجه به اینکه توی صورت سوال نوشته حد پایین n/2 و حد بالای n/3 پس نتیجه میگیریم:اینو چه جوری نتیجه گرفتین؟
[tex]T(\frac{n}2)\leq T(\frac{n}3)[/tex]
صورت سوال دقیقا چی گفته در این مورد.
با اجازه آقا حامد گل.
اگه N رو تو درخت بازگشتی رسم کنیم n/2 دیرتر از n/3 به ۱ میرسه.درنتیجه n/2 کوچکتره. درست میگم آقا حامد.مثلا اگهN=100 باشه ۳/۱۰۰ حدبالاشو خواسته که میشه ۳۴ و ۲/۱۰۰ میشه ۵۰/ معلوم میشه که ۲/N دیرتر به ۱ میرسه.
البته بنده تو کتاب آقای مقسمی روش خوبی رو دیدم. به اینترتیب که n رو با یک عدد جاگذاری کنید و درخت بازگشتیش رو رسم کنید.مثلا بجای n عدد ۸ رو قرار بدید. و بعد تعداد گره هایی که تو درخت ایجاد میشند رو تا وقتیکه در هرشاخه به یک یا شرایط اولیه تابع بازگشتی برسید بشمارید ببینید از چه مرتبه ای هست.مثلا اگه تعداد گره های ایجاد شده ۱۱ باشه جواب نهایی میشه n+3 که از [tex]T({n})[/tex]هستش.البته برای مطمئن شدن باید چند مثال دیگه هم بزنید.مثلا واسه n=16 تعداد گره های ایجاد شده باز هم n+3=19 و برای n=4 تعداد گره های ایجاد شده برابر n+3=7 است.
برای نمونه ای دیگه میتونید [tex]T({n})=T({n-1})*T({n-1})[/tex] و یا [tex]T({n})=T({n-1})-T({n-1})[/tex] رو با روش گفته شده حساب کنید و در نهایت به جواب [tex]T({2^n})[/tex] برسید
(۳۰ دى ۱۳۸۹ ۱۱:۰۸ ق.ظ)sos006 نوشته شده توسط: اگه N رو تو درخت بازگشتی رسم کنیم n/2 دیرتر از n/3 به ۱ میرسه.درنتیجه n/2 کوچکتره.جمله‌ی اولتون درسته ولی [tex]\frac{n}2[/tex]بزرگتره. ۰/۵ >0.33
اینطوری که میگید من صورت سوال را کاملا اشتباه متوجه شدم.فکر کردم منظورتون برای حد بالا و حد پایین در مورد خود تابع بازگشتی است.و طراح خواسته راهنمایی کنه که از راه اصلی حل نکنید.اگر از Tex استفاده میکردید اینطوری نمیشد!
از درخت بازگشت حل میکنیم:
سطح اول: [tex]n[/tex]
سطح دوم: [tex]\frac{5n}{6}[/tex]
سطح سوم: [tex]\frac{5^2n}{6^2}[/tex]
...
در نتیجه:
[tex]n \frac{5n}{6} \frac{5^2n}{6^2} ...=[/tex]
[tex]n(1 \frac{5}{6} \frac{5^2}{6^2} ...)=n(\frac{1}{1-\frac{5}{6}})=6n[/tex]
[tex]T(n)=O(n)[/tex]
(۳۰ دى ۱۳۸۹ ۱۱:۰۸ ق.ظ)sos006 نوشته شده توسط: البته بنده تو کتاب آقای مقسمی روش خوبی رو دیدم.
برای نمونه ای دیگه میتونید [tex]T({n})=T({n-1})*T({n-1})[/tex] و یا [tex]T({n})=T({n-1})-T({n-1})[/tex] رو با روش گفته شده حساب کنید و در نهایت به جواب [tex]T({2^n})[/tex] برسید
موقعی که این قسمت کتاب مقسمی (جدول صفحه‌ی ۶۱) را خوندم گفتم حتما مرتبه رابطه چهارم [tex]T(n)=2T(n-1)[/tex] را اشتباه نوشته بعد که روی رابطه سوم [tex]T(n)=T(n-1)\times T(n-1)[/tex] و پنجم [tex]T(n)=T(n-2)\times T(n-2)[/tex]
دقت کردم متوجه شدم که متاسفانه متاسفانه متاسفانه(!!!) اشتباه از رابطه چهارمی نیست! ایشون هنوز فرق تابع با رابطه بازگشتی را نمیدونند و عنوان جدول را اشتباه نوشتند.اشتباه تایپی هم نبوده مگرنه هیچ وقت [tex]T(n)[/tex] استفاده نمی کردند.اون لحظه یکی از لحظه هایی بود که شک کردم که خواندن این کتاب مفیده یا مضرره!
من منظورتون از حد پایین و بالا رو نفهمیدم ؟!!
مگه این رابطه درست نیست؟؟ پس چرا شما برعکس نوشتین؟؟؟
[tex]T(n/3)=log_{3}^{n}\leq T(n/2)=log_{2}^{n}[/tex]
(۳۰ دى ۱۳۸۹ ۰۳:۵۲ ب.ظ)afagh1389 نوشته شده توسط: من منظورتون از حد پایین و بالا رو نفهمیدم ؟!!بله،درسته.
مگه این رابطه درست نیست؟؟ پس چرا شما برعکس نوشتین؟؟؟
[tex]T(n/3)=log_{3}^{n}\leq T(n/2)=log_{2}^{n}[/tex]
منظورشون بوده از اینا [tex]\left \lfloor x \right \rfloor[/tex] یا اینا [tex]\left \lceil x \right \rceil[/tex]! توی پست قبلی که توضیح دادم:
(۳۰ دى ۱۳۸۹ ۰۲:۲۱ ب.ظ)حامد نوشته شده توسط: اینطوری که میگید من صورت سوال را کاملا اشتباه متوجه شدم.فکر کردم منظورتون برای حد بالا و حد پایین در مورد خود تابع بازگشتی است.و طراح خواسته راهنمایی کنه که از راه اصلی حل نکنید.اگر از Tex استفاده میکردید اینطوری نمیشد!
(۳۰ دى ۱۳۸۹ ۰۴:۰۸ ب.ظ)حامد نوشته شده توسط:[tex]\left \lfloor x \right \rfloor[/tex] یا اینا [tex]\left \lceil x \right \rceil[/tex]اینا توی پست قبلی نبود البته من خودم هم فکر میکردم که منظور اینها باشه ولی بعد گفتم شاید چیز دیگه ای منظورشون بوده.(30 دى ۱۳۸۹ ۰۳:۵۲ ب.ظ)afagh1389 نوشته شده توسط: من منظورتون از حد پایین و بالا رو نفهمیدم ؟!!بله،درسته.
مگه این رابطه درست نیست؟؟ پس چرا شما برعکس نوشتین؟؟؟
[tex]T(n/3)=log_{3}^{n}\leq T(n/2)=log_{2}^{n}[/tex]
منظورشون بوده از اینا [tex]\left \lfloor x \right \rfloor[/tex] یا اینا [tex]\left \lceil x \right \rceil[/tex]! توی پست قبلی که توضیح دادم:
(۳۰ دى ۱۳۸۹ ۰۲:۲۱ ب.ظ)حامد نوشته شده توسط: اینطوری که میگید من صورت سوال را کاملا اشتباه متوجه شدم.فکر کردم منظورتون برای حد بالا و حد پایین در مورد خود تابع بازگشتی است.و طراح خواسته راهنمایی کنه که از راه اصلی حل نکنید.اگر از Tex استفاده میکردید اینطوری نمیشد!