باسلام
t(nرا تتا برحسب بدست آورید
[tex]\left \{ \right.t(n)=2t(\left [ n/logn \right ]) 3n [/tex]
t(1)=1 t(2)=2
(۰۷ آذر ۱۳۹۱ ۰۳:۲۶ ب.ظ)haamidit نوشته شده توسط: باسلام
t(nرا تتا برحسب بدست آورید
[tex]\left \{ \right.t(n)=2t(\left [ n/logn \right ]) 3n [/tex]
t(1)=1 t(2)=2
سلام
من حقیقتش خیلی سعی کردم بفهمم چطوری حل میشه ولی به ذهنم چیزی نرسیده. (شونصد تا کلکم زدم از تغییر متغییر بگیر تا درخت بازگشت و ... )
شما این سوال رو از کجا آوردین ؟
قطعآ مرتبه از نمایی بیشتره. (حتی ولفرام الفا هم برام حلش نکرد)
به جای [tex]\log n[/tex] قرار بدید [tex]\sqrt{n}[/tex]. اینطوری میشه یک مقدار کف نه چندان بد برای [tex]T(n)[/tex] به دست آورد.
---------------
ویرایش: کفی که برای [tex]T(n)[/tex] نوشته بودم غلط بود. پاکش کردم.
(۰۷ آذر ۱۳۹۱ ۱۱:۴۸ ب.ظ)naderx نوشته شده توسط: قطعآ مرتبه از نمایی بیشتره. (حتی ولفرام الفا هم برام حلش نکرد)مرتبه اش نمایی نمی شه.
اینجا بچه ها بهش جواب دادن
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
.
من هم چند بار از روش درخت خواستم به نتیجه برسم اما گیر دارم. بنظرم با درخت حل میشه اما چگونه شو نمی دونم!
یه روش هم هست که حدس بزنی اون که مثلا nlogn تتا ، هست و بعد بیای حد بالا (بیگ او) و حد پایین (اومگای بزرگ) رو حساب کنی بر اساس اون Fn روش دومی رو امتحان نکردم.
(۰۸ آذر ۱۳۹۱ ۰۱:۱۳ ق.ظ)mfXpert نوشته شده توسط: به جای [tex]\log n[/tex] قرار بدید [tex]\sqrt{n}[/tex]. اینطوری میشه یک مقدار کف نه چندان بد برای [tex]T(n)[/tex] به دست آورد. کف [tex]T(n)[/tex] میشه [tex]n\lg \lg n[/tex]ممنون بابت جواب.
رادیکال n، یک فرضیه هست؟ بخاطر اینکه مقدار رادیکال n کمتر از n و بیشتر از logn هست، رادیکال n رو قرار بدیم؟
(۰۷ آذر ۱۳۹۱ ۱۱:۴۸ ب.ظ)naderx نوشته شده توسط:(07 آذر ۱۳۹۱ ۰۳:۲۶ ب.ظ)haamidit نوشته شده توسط: باسلام
t(nرا تتا برحسب بدست آورید
[tex]\left \{ \right.t(n)=2t(\left [ n/logn \right ]) 3n [/tex]
t(1)=1 t(2)=2
سلام
من حقیقتش خیلی سعی کردم بفهمم چطوری حل میشه ولی به ذهنم چیزی نرسیده. (شونصد تا کلکم زدم از تغییر متغییر بگیر تا درخت بازگشت و ... )
شما این سوال رو از کجا آوردین ؟
قطعآ مرتبه از نمایی بیشتره. (حتی ولفرام الفا هم برام حلش نکرد)
طراحی و تحلیل الگوریتمها بهروز قلی زاده
(۰۸ آذر ۱۳۹۱ ۰۱:۱۳ ق.ظ)mfXpert نوشته شده توسط: به جای [tex]\log n[/tex] قرار بدید [tex]\sqrt{n}[/tex]. اینطوری میشه یک مقدار کف نه چندان بد برای [tex]T(n)[/tex] به دست آورد. کف [tex]T(n)[/tex] میشه [tex]n\lg \lg n[/tex]من فکر می کنم [tex]\Theta (n)[/tex] جوابش هست.
به ارسال۳۹ این صفحه نگاه کنین از سمت بالا محدودش کرده.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
از سمت پایین اگه بجای logn مقدار [tex]\sqrt{n}[/tex] قرار بدیم محدود می شه.
تو ارسال ۱۹ صفحه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نشون داده.
دو سمت هر دو مقدار [tex]O(n)[/tex] دارند در اینصورت جواب [tex]\Theta (n)[/tex] هست.
[tex]2T(\frac{n}{\sqrt{n}}) 3n=O(n)<2T(\frac{n}{logn}) 3n<2T(\frac{n}{4}) 3n=O(n)[/tex]
جواب داشت این تست؟
(۰۹ آذر ۱۳۹۱ ۰۷:۱۹ ب.ظ)farhadk نوشته شده توسط: جواب داشت این تست؟
نداشت
(۰۹ آذر ۱۳۹۱ ۰۸:۱۱ ب.ظ)haamidit نوشته شده توسط: نداشتجوابش که طبق قضیه فشار [tex]\Theta( n)[/tex] هست.
ولی چون دو تا مقدار اولیه داده خودش احتمالا باید از طریق معادله مشخصه حل کرده باشه.
بله از طریق قضیه اصلی داریم:
[tex]n^{log_{4}^{2}}=n^{\frac{1}{2}log_{2}^{2}}=\sqrt{n}[/tex]
که [tex]3n=\Theta (n)[/tex] بصورت چند جمله ای بزرگتر از [tex]\sqrt{n}[/tex] هست پس جواب [tex]\Theta (n)[/tex] هست.