10 بهمن 1390, 12:43 ب.ظ
11 بهمن 1390, 04:37 ب.ظ
(10 بهمن 1390 12:43 ب.ظ)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 است.
22 مهر 1392, 08:48 ق.ظ
[tex]t(m)=t(m-1) t(m-2) t(m-3)[/tex]
[tex]x^{3}-x^{2}-x-1=0[/tex]
این معادله مگه اینجوی نیست؟؟
فقط همین جاشو نمیفهمم بقیه شو متوجه شدم،من فک میکنم درجه 3 هست
[tex]x^{3}-x^{2}-x-1=0[/tex]
این معادله مگه اینجوی نیست؟؟
فقط همین جاشو نمیفهمم بقیه شو متوجه شدم،من فک میکنم درجه 3 هست
22 مهر 1392, 06:00 ب.ظ
سلام
جوابش از بیگ اوی n هم بیشتر میشود.
جوابش از بیگ اوی n هم بیشتر میشود.
22 مهر 1392, 09:24 ب.ظ
نه جوابش از مرتبه n میشه. ولی فکر می کنم برای معادله اشتباه کردم و معادله از درجه سه بشه. برای این سوالو از راه درخت جواب بدست میاد. یادم نمیاد چرا این طوری نوشتم.
صفحه 59 حل تمرین clrs جوابو از راه درخت رفته.
صفحه 59 حل تمرین clrs جوابو از راه درخت رفته.
29 مهر 1392, 05:31 ب.ظ
(22 مهر 1392 08:48 ق.ظ)Mahtab.R نوشته شده توسط: [ -> ][tex]t(m)=t(m-1) t(m-2) t(m-3)[/tex]حل بالا کاملا اشتباهه جوابش میشه همین که گفتی از راه ساندویچی ریشه هاش بدست میاد
[tex]x^{3}-x^{2}-x-1=0[/tex]
این معادله مگه اینجوی نیست؟؟
فقط همین جاشو نمیفهمم بقیه شو متوجه شدم،من فک میکنم درجه ۳ هست
(22 مهر 1392 09:24 ب.ظ)Aurora نوشته شده توسط: [ -> ]نه جوابش از مرتبه n میشه. ولی فکر می کنم برای معادله اشتباه کردم و معادله از درجه سه بشه. برای این سوالو از راه درخت جواب بدست میاد. یادم نمیاد چرا این طوری نوشتم.از راه درخت هم احتمالش خیلی ضعیفه جواب درست بدست بیاره یه حد بالا بدست میاره ولی حدش خیلی بالاست فکر کنم D:
صفحه ۵۹ حل تمرین clrs جوابو از راه درخت رفته.
چون یه طرف n/2 و یه طرف n/8 هست شاخه بلنده با کوتاه خیلی باید فرق کنه (البته تجربی میگم شایدم بشه)
29 مهر 1392, 08:15 ب.ظ
منظور شما را متوجه نشدم ولی توی حل تمرین که چک کردم از راه درخت رفته بود عکس زیر هم حل همون صفحه حل تمرین هست.
این جا هم یه راه حل از stackoverflow که راهش سخت بود .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
اگر بتونید ریشه معادله درجه 3 رو بدست بیارید که کمتر از 2 میشه جواب از مرتبه nمیشه.
این جا هم یه راه حل از stackoverflow که راهش سخت بود .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
اگر بتونید ریشه معادله درجه 3 رو بدست بیارید که کمتر از 2 میشه جواب از مرتبه nمیشه.
30 مهر 1392, 02:19 ق.ظ
(29 مهر 1392 08:15 ب.ظ)Aurora نوشته شده توسط: [ -> ]منظور شما را متوجه نشدم ولی توی حل تمرین که چک کردم از راه درخت رفته بود عکس زیر هم حل همون صفحه حل تمرین هست.به نظر درست میاد ولی یه جاهایش اشتباه میزنه مثلا شاخه بلنده log2n هست نه log4n ولی خوب مشکل نداره تو مرتبه
این جا هم یه راه حل از stackoverflow که راهش سخت بود .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
اگر بتونید ریشه معادله درجه ۳ رو بدست بیارید که کمتر از ۲ میشه جواب از مرتبه nمیشه.
فک کنم با قضیه akra nbazzi راحت حل شه