سلام من یه سوال مطرح کردم اما به دلیل اینکه سوال درست بیان نشده بود . موضوع توسط مدیر محترم بسته شد . حالا دوباره مطرحش می کنم.
متن سوال :
در رابطه بازگشتی [tex]T(n)= 9T(\frac{n}{3}) f(n)[/tex] به ازای چند تا از عبارت های[tex]g(n)[/tex] زیر ، دست کم یک تابع برای [tex]f(n)[/tex] وجود دارد به طوری که [tex]T(n) = \Theta (g(n))[/tex] ؟
[tex]n log n||n^{2}||n^{2} log^{2} n ||n^{3}[/tex]
گزینه ی اول : ۱ / گزینه ی دوم : ۲ / گزینه ی سوم : ۳ / گزینه ی چهارم : ۴
جواب :
طبق قضیه ی اصلی [tex]9T(\frac{n}{3})[/tex] داریم : [tex]n^{log_{3}^{9}} = n^{2}[/tex]
حالا اگر [tex]f(n) = n^{3}[/tex] آنگاه [tex]T(n) = n^{3}[/tex]
اگر [tex]f(n) = n^{2}[/tex] آنگاه [tex]T(n) = n^{2} log n[/tex]
اگر [tex]f(n) = n^{2} log n[/tex] آنگاه [tex]T(n) = n^{2} log^{2} n[/tex]
مشکل من در مورد خط قبلی هست که به نظر من طبق قضیه اصلی [tex]T(n) = n^{2}logn[/tex] خواهد شد و نه [tex]T(n) = n^{2} log^{2} n[/tex]. چون در اینجا [tex]f(n)[/tex] بزرگتر از [tex]n^{2}[/tex] است . در ضمن کلید سنجش هم گزینه ی ۳ است . و همچنین این راه حل مربوط به موسسه ی ماهان است.
از کمکتون ممنونم.
خب اگه f رو [tex]n^{2} log^{2} n[/tex] بگیری چون رشدش از [tex]n^{2}[/tex] بیشتره باز جواب خود f میشه. فک کنم واضحه :-؟؟
(۳۰ شهریور ۱۳۹۱ ۰۱:۲۲ ق.ظ)armin_b00ter نوشته شده توسط: خب اگه f رو n^{2} log^{2} n بگیری چون رشدش از n^{2} بیشتره باز جواب خود f میشه. فک کنم واضحه :-؟؟درست می فرمایید بعضی وقت ها یک مسئله ی ساده رو انقدر پیچیده می بینیم که از فهم مسئله عاجز میشیم ، الان که گفتید متوجه شدم و خجالت کشیدم به خاطر طرح سوال! ممنون از شما دوست عزیز .
من بیشتر درگیر اشتباه تایپی که در جواب وجود داشت شدم!
سلام. درختشو بکشیم اینجوری میشه:
سطر اول: [tex]n^{2} log n[/tex]
مجموع سطر دوم: [tex]9 \times (n/3)^{2} log (n/3) = n^2 log (n/3) [/tex]
مجموع سطر سوم: [tex] n^{2} log (n/9) [/tex]
مجموع سطر چهارم: [tex] n^{2} log (n/27) [/tex]
...
تعداد سطرها [tex] log_3 n[/tex] هست. با درنظر گرفتن مبنای ۳ توی لگاریتم پیچیدگی حاصل میشه:
[tex]n^{2} (log n log (n/3) log (n/9) ... log (n/n) = n^2 (log n log n -1 log n -2 ... log n - log n)=n^2 (log n\times log n - log n \time (log n 1)/2 ) \in \theta(n^2 log^2 n) [/tex]
بنظر من جواب درسته.
(۳۰ شهریور ۱۳۹۱ ۰۱:۲۲ ق.ظ)armin_b00ter نوشته شده توسط: خب اگه f رو [tex]n^{2} log^{2} n[/tex] بگیری چون رشدش از [tex]n^{2}[/tex] بیشتره باز جواب خود f میشه. فک کنم واضحه :-؟؟
مطمئنید؟ بنظر من که اگه [tex]f=n^{2} log^{2} n[/tex] پیچیدگی میشه [tex]n^{2} log^{3} n[/tex].
من طبق قضایایی که توی کتاب ها واسه روابط بازگشتی هست این جوابو دادم. در هر صورت جواب تست چه با تعریف شما چه با مال من یکیه. ولی در مورد جواب شما فک میکنم تو مجموع ها اشتباه کردید. یکبار دیگه مجموع ها رو حساب کنید
اصلاح می کنم محاسباتتون درسته
