(۲۳ مهر ۱۳۹۲ ۰۲:۴۷ ب.ظ)tabassomesayna نوشته شده توسط:  سلام دوستان
درمورد سوال زیر چرا جواب گزینه یک میشه ؟ به نظرم تابع f از همه بزرگتره و بعدش g و بعدش هم h.ولی در کتاب نوشته شده که تابع h بزرگتر از f هست.من اینجوری فهمیدم f بیشتره که به جای n چند تا عدد گذاشتم و تابع f بزرگتر شد.یعنی روش من اشتباهه ؟؟

شما دقت کن که [tex]4^{\lg n} = 2 ^{2\lg n} = 2 ^{\lg ^{n^2}} = n ^ 2 (a ^ {log_{c} b} = b ^{ log_{c} a})[/tex] بعد با توجه به این نکته گزینه های ۲ و ۳ و ۴ به راحتی حذف میشن.

(۲۳ مهر ۱۳۹۲ ۰۳:۲۲ ب.ظ)SnowBlind نوشته شده توسط:  

(23 مهر ۱۳۹۲ ۰۲:۴۷ ب.ظ)tabassomesayna نوشته شده توسط:  سلام دوستان
درمورد سوال زیر چرا جواب گزینه یک میشه ؟ به نظرم تابع f از همه بزرگتره و بعدش g و بعدش هم h.ولی در کتاب نوشته شده که تابع h بزرگتر از f هست.من اینجوری فهمیدم f بیشتره که به جای n چند تا عدد گذاشتم و تابع f بزرگتر شد.یعنی روش من اشتباهه ؟؟

شما دقت کن که [tex]4^{\lg n} = 2 ^{2\lg n} = 2 ^{\lg ^{n^2}} = n ^ 2 (a ^ {log_{c} b} = b ^{ log_{c} a})[/tex] بعد با توجه به این نکته گزینه های ۲ و ۳ و ۴ به راحتی حذف میشن.

بله این درست , ولی در قسمت دوم گزینه یک نوشته شده که f از مرتبه ی اُ ی g هست(به این معنی که حد بالای f تابع g هست) در حالیکه f بزرگتر از g هست

(۲۳ مهر ۱۳۹۲ ۰۸:۱۱ ب.ظ)tabassomesayna نوشته شده توسط:  بله این درست , ولی در قسمت دوم گزینه یک نوشته شده که f از مرتبه ی اُ ی g هست(به این معنی که حد بالای f تابع g هست) در حالیکه f بزرگتر از g هست

اگه [tex]\lg n ^ {\lg n}[/tex] منظورتون هست که این میشه [tex]n ^{\lg \lg n}[/tex] که مرتبه این تابع خیلی بیشتر از [tex]n ^ 2[/tex] هستش، به کتاب پوران مراجعه کنید، اونجا نوشته [tex] n^2 < n^3< \lg n ^ {\lg n} < (\frac{3}{2} )^ n[/tex] هر چند [tex]\lg \lg n[/tex] یه جایی از ۲ بیشتر میشه مثلا ۳۲ که این تابع از n ^ 2 بیشتر میشه و به همین ترتیب برای n های بزرگ تر

(۲۳ مهر ۱۳۹۲ ۰۹:۳۷ ب.ظ)SnowBlind نوشته شده توسط:  

(23 مهر ۱۳۹۲ ۰۸:۱۱ ب.ظ)tabassomesayna نوشته شده توسط:  بله این درست , ولی در قسمت دوم گزینه یک نوشته شده که f از مرتبه ی اُ ی g هست(به این معنی که حد بالای f تابع g هست) در حالیکه f بزرگتر از g هست

اگه [tex]\lg n ^ {\lg n}[/tex] منظورتون هست که این میشه [tex]n ^{\lg \lg n}[/tex] که مرتبه این تابع خیلی بیشتر از [tex]n ^ 2[/tex] هستش، به کتاب پوران مراجعه کنید، اونجا نوشته [tex] n^2 < n^3< \lg n ^ {\lg n} < (\frac{3}{2} )^ n[/tex] هر چند [tex]\lg \lg n[/tex] یه جایی از ۲ بیشتر میشه مثلا ۳۲ که این تابع از n ^ 2 بیشتر میشه و به همین ترتیب برای n های بزرگ تر

ممنون از توضیحتون
من n های بزرگتر رو در نظر نگرفته بودم به خاطر همین اشتباه کردم.بازم ممنون