سلام دوستان
من این سوال رو متوجه نشدم اگه میشه با مثال توضیح بدید ممنون میشم
(۲۳ فروردین ۱۳۹۴ ۰۵:۵۲ ب.ظ)post98 نوشته شده توسط: سلام دوستان
من این سوال رو متوجه نشدم اگه میشه با مثال توضیح بدید ممنون میشم
من ابتدا پاسخ سوال میدم و بعد در مورد خواص حدی نمادهای مجانبی O بزرگ صحبت می کنیم و چندتا مثال می زنیم تا متوجه بشیم:
از [tex]\lim_{n\longrightarrow\infty}\frac{f(n)}{g(n)}= \infty[/tex] می توان نتایج زیر را گرفت:
[tex]g(n)\in O(f(n))[/tex]
[tex]g(n)\in o(f(n))[/tex]
[tex]f(n)\in Omega(g(n))[/tex]
[tex]f(n)\in\omega(g(n))[/tex]
[tex]f(n)\notin Theta(g(n))[/tex]
[tex]g(n)\notin Theta(f(n))[/tex]
که با این اطلاعات، بنابراین گزینه ۳ صحیح است.
- خواص حدی نماد O:
وقتی داشته باشیم [tex]f(n)\in O(g(n))[/tex]، دو حالت (الف) [tex]f(n)\notin Theta(g(n))[/tex] و (ب) [tex]f(n)\in Theta(g(n))[/tex] را خواهیم داشت که از لحاظ حدی به صورت زیر خواهند بود:
الف) [tex]\lim_{n\longrightarrow\infty}\frac{g(n)}{f(n)}=\infty[/tex]
این نتیجه رو زمانی خواهیم داشت که [tex]f(n)<c(g(n))[/tex] یعنی به عبارتی [tex]f(n)\in o(g(n))[/tex] یا [tex]f(n)\in O(g(n))[/tex] و [tex]f(n)\notin Theta(g(n))[/tex] باشد. مثلاً توابع [tex]f(n)=3n^2[/tex] و [tex]g(n)=n^3[/tex] را در نظر بگیرید، اگر حد زیر را بگیریم، خواهیم داشت:
[tex]\lim_{n\longrightarrow\infty}\frac{g(n)}{f(n)}=\lim_{n\longrightarrow\infty}\frac{n^3}{3n^2}=\lim_{n\longrightarrow\infty}\frac{n}{3}=\infty[/tex]
در واقع چون سرعت رشد g(n) بیشتر از f(n) هست، بنابراین برای nهای خیلی بزرگ به بی نهایت میل می کند.
در این حالت همچین خواهیم داشت:
[tex]\lim_{n\longrightarrow\infty}\frac{f(n)}{g(n)}=0[/tex]
ب) [tex]\lim_{n\longrightarrow\infty}\frac{g(n)}{f(n)}=cte[/tex] (عدد ثابت = cte)
این نتیجه رو زمانی خواهیم داشت که [tex]c_1g(n)\le f(n)\le c_2g(n)[/tex] یعنی به عبارتی [tex]f(n)\in Theta(g(n))[/tex] باشد. مثلاً توابع [tex]f(n)=3n^2[/tex] و [tex]g(n)=n^2[/tex] را در نظر بگیرید، اگر حد زیر را بگیریم، خواهیم داشت:
[tex]\lim_{n\longrightarrow\infty}\frac{g(n)}{f(n)}=\lim_{n\longrightarrow\infty}\frac{n^2}{3n^2}=\lim_{n\longrightarrow\infty}\frac{1}{3}=\frac{1}{3}[/tex]
در این حالت واضح است که وقتی [tex]f(n)\in O(g(n))[/tex] و [tex]f(n)\in Theta(g(n))[/tex] باشد، [tex]g(n)\in Omega(f(n))[/tex] نیز می باشد.
در این حالت همچین خواهیم داشت:
[tex]\lim_{n\longrightarrow\infty}\frac{f(n)}{g(n)}=cte[/tex] (عدد ثابت = cte)
در این تست هم، عکس حالت الف مورد سوال قرار گرفته است.
(اگر نیاز به توضیح بیشتری داره، بفرمائید تا توضیح بدم.)