[/quote]

پاسخ هاتون کامل و جامع بود واقعا خسته نباشید
فقط طی این سوالی که پیوست کرده ام کتاب طراحی الگوریتم مدرسان شریف $\log^5n<n^{.4}$ را غلط دونسته (لگاریتم به توان ۵ و n به توان چهار دهم)

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

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

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

$n^{0.4}>\log^5n\:$

فرض کنیم که : $n=2^x$

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

$2^{0.4x}>\log^52^x=x^5 \Longrightarrow\Longrightarrow\Longrightarrow \: \: \: \: 2^{0.4x}>x^5$

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

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

$0.4x>\: 5\log x \Longrightarrow\Longrightarrow x>12.5\log x$

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

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

خیلی خیلی ممنون
تو این سوال پس گزینه ی $3^{\log n}<n^2\log n$ هم درست است؟

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

$n^{0.4}>\log^5n\:$

فرض کنیم که : $n=2^x$

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

$2^{0.4x}>\log^52^x=x^5 \Longrightarrow\Longrightarrow\Longrightarrow \: \: \: \: 2^{0.4x}>x^5$

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

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

$0.4x>\: 5\log x \Longrightarrow\Longrightarrow x>12.5\log x$

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

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

---

************************
بله گزینه آخر هم صحیحه