سوال زیر بارها به همین صورت یا به صورت کاملاً مشابه سوال آزمون مهندسی کامپیوتر . IT بوده
[tex]f(n)=4^{lg n}=n^{lg4}=n^{2}[/tex]
[tex]g(n)=lg^{lgn}n=n^{lg lgn}[/tex]
[tex]lg^{2}n<n^{2}<n^{lglgn}[/tex]
[tex]g(n)=lg^{lgn}n=n^{lg lgn}[/tex]
[tex]lg^{2}n<n^{2}<n^{lglgn}[/tex]
(۰۸ مرداد ۱۳۹۰ ۱۱:۱۲ ب.ظ)Masoud05 نوشته شده توسط: بچه‌ها خیلی راحت میشه با عدد گزاری جواب رو بدست آورد( راه تستی از نظر من )البته میشه از راه های تحلیلی هم پیش رفت .
به هر حال n= 1024 در نظر بگیرید( یه عدد که توانی از ۲ باشه ).
مقدار‌ها رو که بدست بیارید میبینید که گزینه ۱ درسته .البته راه حل اصلی اونم بعداً میزارم . فعلاً منتظر حضورگرم شما هستم!!!
عدد گذاری فک نکنم جواب بده. چندان قابل اعتماد نیست. اگه به نمودار های نماد های مجانبی نگاهی بندازید می بینید که ابتدای نمودار حالتشون stable نیست و جواب غلطی نشون میدن و تنها از یک اندازه مشخص ورودی به بعده که نمادها اونطوری که میشناسیمشون رفتار می کنن.
می دانیم:
[tex]log a^{{\color{Red} n}}={\color{Red} n} log a[/tex]
از دو طرف تساوی log می گیریم:
[tex]log f(n)=log 4^{{\color{Red} log n}}={\color{Red} log n} log4=2logn[/tex]
[tex]log g(n)=loglog^{{\color{Red} log n}}n={\color{Red} logn}loglogn={\color{Red} logn}loglogn[/tex]
[tex]log h(n)=log log^{{\color{Red} 2}}n={\color{Red} 2}loglogn[/tex]
در نتیجه:
[tex]g(n)>f(n)>h(n)[/tex]
چون [tex]f(n)\in O(g(n))[/tex] یعنی [tex]f(n)\leq cg(n)[/tex]
و [tex]f(n)\in \Omega (h(n))[/tex] یعنی [tex]f(n)\geq ch(n)[/tex]
پس گزینه ۱ صحیح است.
(۰۹ مرداد ۱۳۹۰ ۱۲:۱۷ ق.ظ)ehsan_nekooee نوشته شده توسط:(08 مرداد ۱۳۹۰ ۱۱:۱۲ ب.ظ)Masoud05 نوشته شده توسط: بچه‌ها خیلی راحت میشه با عدد گزاری جواب رو بدست آورد( راه تستی از نظر من )البته میشه از راه های تحلیلی هم پیش رفت .
به هر حال n= 1024 در نظر بگیرید( یه عدد که توانی از ۲ باشه ).
مقدار‌ها رو که بدست بیارید میبینید که گزینه ۱ درسته .البته راه حل اصلی اونم بعداً میزارم . فعلاً منتظر حضورگرم شما هستم!!!
عدد گذاری فک نکنم جواب بده. چندان قابل اعتماد نیست. اگه به نمودار های نماد های مجانبی نگاهی بندازید می بینید که ابتدای نمودار حالتشون stable نیست و جواب غلطی نشون میدن و تنها از یک اندازه مشخص ورودی به بعده که نمادها اونطوری که میشناسیمشون رفتار می کنن.
آفرین درسته، برا همین من یه مقدار بزرگ که راحت هم بشه حسابش کرد رو امتحان کردم چراکه اعداد کوچک مثلاً در توابع خطی از در جه ۲ میتونه مقدار بزرگتری رو بده اما این مقدار یه خورده برای عدد مثل ۱۰۲۴ بعیده مگه اینکه پشت تابع خطی یه عدد بزرگی باشه که شما می تونید اونو بررسی کنید . در ضمن من گفتم یه راه سریع . شما راحت می تونید با استفاده از قواعد ریاضی مثل قاعده ای که عدد به توان لگاریتم رو به راحتی با تعویض پایه و مقدار لگاریتم به یه تابع درجه n تبدیل میکنه به جواب برسید اما من جواب رو نمیزارم تا بچه‌ها بیان بحث کنن.
راه حل همون ارسال بالاییه اما با روشی که من گفتم توی ۳ سوت این مسئله رو حل میکنید