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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

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

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

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

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

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

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

نمودار این ۴ تابع وقتی '"`UNIQ--postMath-0000001B-QINU`"'

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

نمودار۲.jpg

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

نمودار ۳.jpg

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

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

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

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

یا و یا

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

یا

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

نماد O بزرگ

منابع[ویرایش]