(۱۹ اردیبهشت ۱۳۹۴ ۰۳:۳۰ ب.ظ)gunnersregister نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۴ ۱۲:۵۷ ب.ظ)فاطمه ارشد ای تی نوشته شده توسط:  فقط طی این سوالی که پیوست کرده ام کتاب طراحی الگوریتم مدرسان شریف [tex]\log^5n<n^{.4}[/tex] را غلط دونسته (لگاریتم به توان ۵ و n به توان چهار دهم)

البته این نمیتونه غلط باشه . دلیلش هم اینه:

[tex]n^{0.4}>\log^5n\: [/tex]

فرض کنیم که : [tex]n=2^x[/tex]

پس خواهیم داشت:

[tex]2^{0.4x}>\log^52^x=x^5 \Longrightarrow\Longrightarrow\Longrightarrow \: \: \: \: 2^{0.4x}>x^5[/tex]

و همانطور که میدانیم رشد توابع نمایی از رشد توابع چند جمله ای بیشتر است ولی اگر ادامه بدهیم به یک مقدار مرزی دقیق میرسیم.

از طرفین عبارت بالا [tex]\log[/tex] بگیریم خواهیم داشت:

[tex]0.4x>\: 5\log x \Longrightarrow\Longrightarrow x>12.5\log x[/tex]

این رابطه تقریبا برای [tex]x\ge80[/tex]
صحیح می باشد پس نتیجه میگیریم که رابطه اصلی هم برای [tex]n\ge2^{80}[/tex] صحیح است.

کتابهای تست معمولا ایراداتی دارن و خالی از اشکال نیستن.