هوالعلیم
[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{4}) T(\frac{n}{8}) n[/tex]
(۱۰ بهمن ۱۳۹۰ ۱۲:۴۳ ب.ظ)yaali نوشته شده توسط: هوالعلیم
[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{4}) T(\frac{n}{8}) n[/tex]
[tex]n=2^m[/tex]
[tex]t(2^m)=T(\frac{2^m}{2}) T(\frac{2^m}{4}) T(\frac{2^m}{8}) 2^m[/tex]
[tex]t(2^m)=T({2^{m-1}}) T({2^{m-2}}) T({2^{m-3}}) 2^m[/tex]
[tex]t(m)=T({{m-1}}) T({{m-2}}) T({{m-3}}) 2^m[/tex]
ناهمگن
[tex]x^2-x-1=0[/tex]
[tex]x=\frac{-1 \sqrt{5}}{2},x=\frac{-1-\sqrt{5}}{2}[/tex]
[tex]2^m\Rightarrow (m-2)^1[/tex]
پس ۳ تا ریشه متمایز داریم
[tex](\frac{-1 \sqrt{5}}{2})^m (\frac{-1-\sqrt{5}}{2})^m 2^m[/tex]
و با m=logn
[tex](\frac{-1 \sqrt{5}}{2})^{logn} (\frac{-1-\sqrt{5}}{2})^{log n} 2^{logn}[/tex]
جواب آخر بزرگترین عبارت است:
[tex]2^{logn}=n[/tex]
پس جواب از مرتبه n است.
[tex]t(m)=t(m-1) t(m-2) t(m-3)[/tex]
[tex]x^{3}-x^{2}-x-1=0[/tex]
این معادله مگه اینجوی نیست؟؟
فقط همین جاشو نمیفهمم بقیه شو متوجه شدم،من فک میکنم درجه ۳ هست
سلام
جوابش از بیگ اوی n هم بیشتر میشود.
نه جوابش از مرتبه n میشه. ولی فکر می کنم برای معادله اشتباه کردم و معادله از درجه سه بشه. برای این سوالو از راه درخت جواب بدست میاد. یادم نمیاد چرا این طوری نوشتم.
صفحه ۵۹ حل تمرین clrs جوابو از راه درخت رفته.
(۲۲ مهر ۱۳۹۲ ۰۸:۴۸ ق.ظ)Mahtab.R نوشته شده توسط: [tex]t(m)=t(m-1) t(m-2) t(m-3)[/tex]حل بالا کاملا اشتباهه جوابش میشه همین که گفتی از راه ساندویچی ریشه هاش بدست میاد
[tex]x^{3}-x^{2}-x-1=0[/tex]
این معادله مگه اینجوی نیست؟؟
فقط همین جاشو نمیفهمم بقیه شو متوجه شدم،من فک میکنم درجه ۳ هست
(۲۲ مهر ۱۳۹۲ ۰۹:۲۴ ب.ظ)Aurora نوشته شده توسط: نه جوابش از مرتبه n میشه. ولی فکر می کنم برای معادله اشتباه کردم و معادله از درجه سه بشه. برای این سوالو از راه درخت جواب بدست میاد. یادم نمیاد چرا این طوری نوشتم.از راه درخت هم احتمالش خیلی ضعیفه جواب درست بدست بیاره یه حد بالا بدست میاره ولی حدش خیلی بالاست فکر کنم D:
صفحه ۵۹ حل تمرین clrs جوابو از راه درخت رفته.
چون یه طرف n/2 و یه طرف n/8 هست شاخه بلنده با کوتاه خیلی باید فرق کنه (البته تجربی میگم شایدم بشه)
منظور شما را متوجه نشدم ولی توی حل تمرین که چک کردم از راه درخت رفته بود عکس زیر هم حل همون صفحه حل تمرین هست.
![[تصویر: 221382_68072260510892723861.png]](https://img.manesht.ir/221382_68072260510892723861.png)
این جا هم یه راه حل از stackoverflow که راهش سخت بود .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اگر بتونید ریشه معادله درجه ۳ رو بدست بیارید که کمتر از ۲ میشه جواب از مرتبه nمیشه.
(۲۹ مهر ۱۳۹۲ ۰۸:۱۵ ب.ظ)Aurora نوشته شده توسط: منظور شما را متوجه نشدم ولی توی حل تمرین که چک کردم از راه درخت رفته بود عکس زیر هم حل همون صفحه حل تمرین هست.به نظر درست میاد ولی یه جاهایش اشتباه میزنه مثلا شاخه بلنده log2n هست نه log4n ولی خوب مشکل نداره تو مرتبه
این جا هم یه راه حل از stackoverflow که راهش سخت بود .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اگر بتونید ریشه معادله درجه ۳ رو بدست بیارید که کمتر از ۲ میشه جواب از مرتبه nمیشه.
فک کنم با قضیه akra nbazzi راحت حل شه
(۰۱ آبان ۱۳۹۲ ۰۲:۳۹ ق.ظ)mohammad.ardeshiri نوشته شده توسط: من بلد نیستم این روابط رو تایپ کنم
پاسخ جدید رو بزنید پایین کادر
نوشتن فرمول در tex هست