(۲۳ فروردین ۱۳۹۴ ۰۵:۵۲ ب.ظ)post98 نوشته شده توسط:  سلام دوستان

من این سوال رو متوجه نشدم اگه میشه با مثال توضیح بدید ممنون میشم

من ابتدا پاسخ سوال میدم و بعد در مورد خواص حدی نمادهای مجانبی O بزرگ صحبت می کنیم و چندتا مثال می زنیم تا متوجه بشیم:

از $\lim_{n\longrightarrow\infty}\frac{f(n)}{g(n)}= \infty$ می توان نتایج زیر را گرفت:
$g(n)\in O(f(n))$
$g(n)\in o(f(n))$
$f(n)\in Omega(g(n))$
$f(n)\in\omega(g(n))$
$f(n)\notin Theta(g(n))$
$g(n)\notin Theta(f(n))$

که با این اطلاعات، بنابراین گزینه ۳ صحیح است.

- خواص حدی نماد O:
وقتی داشته باشیم $f(n)\in O(g(n))$، دو حالت (الف) $f(n)\notin Theta(g(n))$ و (ب) $f(n)\in Theta(g(n))$ را خواهیم داشت که از لحاظ حدی به صورت زیر خواهند بود:
الف) $\lim_{n\longrightarrow\infty}\frac{g(n)}{f(n)}=\infty$
این نتیجه رو زمانی خواهیم داشت که $f(n)<c(g(n))$ یعنی به عبارتی $f(n)\in o(g(n))$ یا $f(n)\in O(g(n))$ و $f(n)\notin Theta(g(n))$ باشد. مثلاً توابع $f(n)=3n^2$ و $g(n)=n^3$ را در نظر بگیرید، اگر حد زیر را بگیریم، خواهیم داشت:
$\lim_{n\longrightarrow\infty}\frac{g(n)}{f(n)}=\lim_{n\longrightarrow\infty}\fra​c{n^3}{3n^2}=\lim_{n\longrightarrow\infty}\frac{n}{3}=\infty$
در واقع چون سرعت رشد g(n) بیشتر از f(n) هست، بنابراین برای nهای خیلی بزرگ به بی نهایت میل می کند.
در این حالت همچین خواهیم داشت:
$\lim_{n\longrightarrow\infty}\frac{f(n)}{g(n)}=0$

ب) $\lim_{n\longrightarrow\infty}\frac{g(n)}{f(n)}=cte$ (عدد ثابت = cte)
این نتیجه رو زمانی خواهیم داشت که $c_1g(n)\le f(n)\le c_2g(n)$ یعنی به عبارتی $f(n)\in Theta(g(n))$ باشد. مثلاً توابع $f(n)=3n^2$ و $g(n)=n^2$ را در نظر بگیرید، اگر حد زیر را بگیریم، خواهیم داشت:
$\lim_{n\longrightarrow\infty}\frac{g(n)}{f(n)}=\lim_{n\longrightarrow\infty}\fra​c{n^2}{3n^2}=\lim_{n\longrightarrow\infty}\frac{1}{3}=\frac{1}{3}$
در این حالت واضح است که وقتی $f(n)\in O(g(n))$ و $f(n)\in Theta(g(n))$ باشد، $g(n)\in Omega(f(n))$ نیز می باشد.
در این حالت همچین خواهیم داشت:
$\lim_{n\longrightarrow\infty}\frac{f(n)}{g(n)}=cte$ (عدد ثابت = cte)

در این تست هم، عکس حالت الف مورد سوال قرار گرفته است.
(اگر نیاز به توضیح بیشتری داره، بفرمائید تا توضیح بدم.)