باز کردن منو اصلی

در نظریه پیچیدگی محاسباتی علاوه بر نماد O بزرگ، نمادهای دیگری همچون امگای بزرگ()، امگای کوچک:()، تتا() و o کوچک() نیز وجود دارند

نماد امگای بزرگ به‌طور شهودی بیان می‌کند که اگر برای دو تابع و داشته باشیم در مقادیر بسیار بزرگ n یا به عبارتی وقتی n به سمت بی‌نهایت میل می‌کند٫ تابع از ضریب ثابتی از تابع g بزرگتر خواهد شد یا به عبارتی تابع از مرتبهٔ تابع خواهد شد.

برای مثال اگر زمان اجرای تابعی از باشد برای ‌های به قدر کافی بزرگ زمان اجرای تابع حداقل (به ازای یک عدد ثابت ) خواهد بود

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

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

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

 

 

 

 

 

یک مثالویرایش

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

 

 

 

 

رفتار این چهار تابع را طبق نمودارشان بررسی می‌کنیم. در ابتدا به نظر می‌رسد تابع   با توجه به ضریب بزرگتری که دارد مقدارهای بزرگتری نیز داشته باشد که برای   هم همین‌گونه است.

اما با بزرگ شدن مقدار   رفتار تابع‌ها نیز نسبت به هم متفاوت می‌شود. شکل زیر رفتار توابع را وقتی   است نشان می‌دهد. ملاحظه می‌شود که تابع   به‌تدریج مقدارش از سایر توابع بیشتر می‌شود

با بزرگتر شدن   وضعیت به این شکل در می‌آید: به‌تدریج تابع   از بقیه توابع بیش‌تر می‌شود.

و برای مقدار بزرگ   داریم:

تابع   کاملاً بقیه توابع بیش‌تر می‌شود.

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

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

  یا  و   یا  

  زیرا تابع   همواره حدودا دوبرابر تابع   است و مرتبهٔ یکسانی دارند.

  یا 

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

منابعویرایش