نماد O بزرگ

‫در نظریهٔ پیچیدگی محاسبا‌تی، نماد O بزرگ (به انگلیسی: Big O notation)‏ برای نشان دادن رابطه میان تعداد داده‌ها و منابع محاسباتی مورد نیاز برای حل یک مسأله با استفاده از یک الگوریتم استفاده می‌شود. استفاده از این نماد معمولاً برای بررسی زمان و یا حافظه مورد نیاز برای حل مسأله‌ای با تعداد زیادی ورودی می‌باشد.

در ریاضیات علامت O بزرگ رفتار حدی یک تابع را وقتی آرگومان‌های آن به یک عدد خاص یا به بینهایت میل می‌کند، توصیف می‌کند.علامت O بزرگ به کاربر اجازه می‌دهد که تابع را ساده کند تا بر روی نرخ رشد آن متمرکز شود. بنابراین توابع مختلف با نرخ رشد یکسان می‌توانند دارای یک علامت O مشابه باشند.

هرچند این علامت به عنوان بخشی از ریاضیات محض گسترش یافت ولی هم اکنون در تئوری‌های پیچیدگی محاسبات هم مکرراً استفاده می‌شود. بدترین حالت یا حالت میانگین زمان اجرا یا حافظه مورد استفاده یک الگوریتم غالباً به صورت تابعی از طول داده ورودی با استفاده از علامت O بزرگ توصیف می‌شود.

این به طراحان الگوریتم اجازه می‌دهد که رفتار الگوریتم هایشان را پیش بینی کنند و تصمیم بگیرند که کدام الگوریتم را استفاده کنند(بدون توجه به معماری کامپیوتر یا میزان آهنگ ساعت آن).

وقتی تابعی را با استفاده از علامت O بزرگ توصیف می‌کنیم معمولاً تنها یک کران بالا برای نرخ رشد آن تابع فراهم می‌کنیم. علامت‌های مرتبط دیگر برای توصیف توابع عبارتند از: o, Ω, ω, Θ.

تعریف رسمی

فرض کنید (f (x) ,g (x توابعی باشند که روی زیرمجموعه‌ای از اعداد حقیقی تعریف شده باشند آنگاه داریم:

$f(x)=O(g(x))\mbox{ as }x\to\infty\,$

اگر و تنها اگر عدد حقیقی مثبت M و عدد حقیقی x ₀ موجود باشد به طوری که:

$|f(x)| \le \; M |g(x)|\mbox{ for all }x>x_0.$

این علامت برای توصیف رفتار تابع نزدیک یک عدد حقیقی مانند a (معمولاً, a = 0) نیز به کار می‌رود:

$f(x)=O(g(x))\mbox{ as }x\to a\,$

اگر و تنها اگر عدد مثبتی مانند δ و M موجود باشند به طوری که:

$|f(x)| \le \; M |g(x)|\mbox{ for }|x - a| < \delta.$

مثال

اگر زمان، (T(n، لازم برای حل مسأله‌ای با n ورودی برابر باشد با:

$T(n)=4n^2-5n+7$

آنگاه اگر تعداد ورودی این مسأله به بی‌نهایت میل کند اندازه جمله $n^2$ بسیار بزرگتر از دیگر جمله‌ها خواهد بود. در این صورت گفته می‌شود:

$T(n)\in O(n^2)$

و یا:

$T(n)= O(n^2)$

این بدان معنی است که اگر تعداد ورودی ۲ برابر شود زمان حل (با فرض زیاد بودن تعداد ورودی) ۴ برابر خواهد شد.

در استفاده معمولی تعریف دقیق و رسمی علامت O مورد استفاده قرار نمی‌گیرد بلکه علامت O بزرگ برای تابع (f (x به صورت زیر ساده می‌شود:

• اگر (f (xمجموع توابع مختلف باشد، تابع با سرعت رشد بیشتر را نگه داشته و بقیه را حذف می‌کنیم.

• اگر (f (xمضربی از چند فاکتور مختلف باشد هر مقدار ثابتی را حذف می‌کنیم.

به عنوان مثال فرض کنید

f (x) = 6x⁴ − 2x³ + 5

و ما می‌خواهیم این تابع را با استفاده از علامت O بزرگ ساده کنیم، این تابع مجموع سه تابع 6x⁴, −2x³، و 5 است. تابع با نرخ رشد سریع تر همان تابع از مرتبه بیشتر است یعنی: 6x⁴. حال قانون دوم را اجرا می‌کنبم:

6x⁴ ضرب 6 و x⁴ است که اولی به x وابسته نیست بنابراین آن را حذف می‌کنیم و تنها x⁴ می‌ماند در نتیجه : (f (x) = O (x⁴

فواید

علامت O بزرگ دو دامنه کاربرد دارد:

• در ریاضیات معمولاً برای نشان دادن این که یک سری هندسی متناهی تا چه اندازه به تابع مورد نظر نزدیک است، خصوصاً در مورد سری تیلور ناقص از این علامت استفاده می‌شود.

• در علوم کامپیوتر این علامت در تحلیل الگوریتم‌ها کاربرد دارد.

در هر دو کاربرد تابع (g (xکه در O(...) به گونه‌ای انتخاب می‌شود که تا حد امکان ساده باشد.

تاریخچه

علامت O بزرگ اولین بار توسط متخصص اعداد Paul Bachmann در سال 1894، در جلد دوم کتاب Analytische Zahlentheorie معرفی شد (که جلد اولش در سال 1892 چاپ شده و شامل این علامت نبود). این علامت در کارهای نظریه اعداد توسط Edmund Landau متداول شد و به همین خاطر گاهی از آن به نام Landau symbol یاد می‌شود.

این علامت در علوم کامپیوتر توسط دانلد کنوت (که علامت‌های مربوطه امگا و تتا را نیز برای اولین بار معرفی کرد) مشهور شد.او هم چنین متذکر شد که علامت امگا توسط Hardy و Littlewood تحت معنی اندکی متفاوت قبلاً تعریف شده بوده‌است.

منابع

• دانلد کنوت. Big Omicron and big Omega and big Theta, ACM SIGACT News, Volume 8, Issue 2, 1976.
• Nicholas J. Higham,Handbook of writing for the mathematical sciences, SIAM. ISBN 0-89871-420-6, p. 25
• http://en.wikipedia.org/wiki/Big_O_notation