نماد امگا بزرگ

در نظریه پیچیدگی محاسباتی علاوه بر نماد O بزرگ، نمادهای دیگری همچون امگای بزرگ(${\displaystyle \Omega }$)، امگای کوچک:(${\displaystyle \omega }$)، تتا(${\displaystyle \Theta }$) و o کوچک(${\displaystyle o}$) نیز وجود دارند

نماد امگای بزرگ به‌طور شهودی بیان می‌کند که اگر برای دو تابع ${\displaystyle f}$ و ${\displaystyle g}$ داشته باشیم ${\displaystyle f(n)=\Omega (g(n))}$ در مقادیر بسیار بزرگ n یا به عبارتی وقتی n به سمت بی‌نهایت میل می‌کند٫ تابع ${\displaystyle f}$ از ضریب ثابتی از تابع g بزرگتر خواهد شد یا به عبارتی تابع ${\displaystyle g}$ از مرتبهٔ تابع ${\displaystyle f}$ خواهد شد.

برای مثال اگر زمان اجرای تابعی از ${\displaystyle \Omega (f(n))}$ باشد برای ${\displaystyle n}$‌های به قدر کافی بزرگ زمان اجرای تابع حداقل ${\displaystyle k.f(n)}$(به ازای یک عدد ثابت ${\displaystyle k}$) خواهد بود

این نماد در واقع برعکس نماد O بزرگ است یعنی:

${\displaystyle f(n)=\Omega (g(n))\Leftrightarrow g(n)=O(f(n))}$

تعریف ریاضی نمادها

تعریف ریاضی هریک از نمادهای بالا این‌گونه است:

${\displaystyle f(n)=O(g(n))\Leftrightarrow \exists k:\exists n_{0}:\forall n\geq n_{0}:f(n)\leq k.g(n)}$

${\displaystyle f(n)=o(g(n))\Leftrightarrow \forall k:\exists n_{0}:\forall n\geq n_{0}:f(n)\leq k.g(n)}$

${\displaystyle f(n)=\Omega (g(n))\Leftrightarrow \exists k:\exists n_{0}:\forall n\geq n_{0}:f(n)\geq k.g(n)}$

${\displaystyle f(n)=\omega (g(n))\Leftrightarrow \forall k:\exists n_{0}:\forall n\geq n_{0}:f(n)\geq k.g(n)}$

${\displaystyle f(n)=\Theta (g(n))\Leftrightarrow f(n)=\Omega (g(n)),f(n)=O(g(n))}$

یک مثال

چهار تابع زیر را در نظر بگیرید:

${\displaystyle f(n)=1000n^{2}+20n+16}$

${\displaystyle g(n)=2n^{3}+100n^{\tfrac {4}{3}}+56}$

${\displaystyle h(n)=n^{3}-{\frac {1}{2}}n^{2}+{\frac {1}{3}}n}$

${\displaystyle i(n)={\frac {1}{1000}}n^{4}}$

رفتار این چهار تابع را طبق نمودارشان بررسی می‌کنیم. در ابتدا به نظر می‌رسد تابع ${\displaystyle f}$ با توجه به ضریب بزرگتری که دارد مقدارهای بزرگتری نیز داشته باشد که برای ${\displaystyle n\leq 100}$ هم همین‌گونه است.

نمودار این ۴ تابع وقتی ${\displaystyle n\leq 100}$

اما با بزرگ شدن مقدار ${\displaystyle n}$ رفتار تابع‌ها نیز نسبت به هم متفاوت می‌شود. شکل زیر رفتار توابع را وقتی ${\displaystyle n\leq 1000}$ است نشان می‌دهد. ملاحظه می‌شود که تابع ${\displaystyle g}$ به‌تدریج مقدارش از سایر توابع بیشتر می‌شود

با بزرگتر شدن ${\displaystyle n}$ وضعیت به این شکل در می‌آید: به‌تدریج تابع ${\displaystyle i}$ از بقیه توابع بیش‌تر می‌شود.

و برای مقدار بزرگ ${\displaystyle n}$ داریم:

تابع ${\displaystyle i}$ کاملاً بقیه توابع بیش‌تر می‌شود.

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

طبق تعاریف بالا می‌تواین رابطهٔ این توابع را برحسب نمادگذاری‌های گفته شده بیان کنیم:

${\displaystyle f(n)=O(g(n))}$ یا ${\displaystyle f(n)=o(g(n))}$و ${\displaystyle g(n)=\Omega (f(n))}$ یا ${\displaystyle g(n)=\omega (f(n))}$

${\displaystyle g(n)=\Theta (h(n))}$ زیرا تابع ${\displaystyle g}$ همواره حدودا دوبرابر تابع ${\displaystyle h}$ است و مرتبهٔ یکسانی دارند.

${\displaystyle h(n)=O(i(n))}$ یا${\displaystyle h(n)=o(i(n))}$

جستارهای وابسته

• نماد O بزرگ

منابع

• ویکی‌پدیای انگلیسی نماد O بزرگ
• نماد o کوچک