نماد O بزرگ

نماد O بزرگ (به انگلیسی: Big O notation) یک نماد ریاضیاتی ست که برای توصیف رفتار حدی یک تابع (وقتی آرگومان‌های آن به بی‌نهایت میل کند) به کار می‌رود.

این نماد (مخفف Order of growth (به فارسی: مرتبهٔ رشد)) اولین بار برای تحلیل سرعت الگوریتم‌های رایانشی ابداع شد و بعدها به حسابان و نظریّهٔ اعداد گسترش یافت.

در علوم رایانه و نظریهٔ پیچیدگی محاسباتی، این نماد برای تحلیل الگوریتم‌ها و دسته‌بندی و مقایسهٔ الگوریتم‌های متفاوتِ موجود برای حل یک مسئلهٔ خاص به کار می‌رود. پیچیدگی محاسباتی نشان‌دهندهٔ رابطهٔ میان «داده‌ها» با «مقدار زمان یا مقدار حافظهٔ مورد نیاز برای پیدا کردن جواب» است و برای توصیف آن از این نماد استفاده می‌شود.

در نظریهٔ تحلیلی اعداد، این نماد برای توصیف میزان دقت یک تقریب به کار می‌رود. یکی از مثال‌های معروف این موضوع در قضیهٔ اعداد اول است: اگر $\pi (x)$ تعداد اعداد اول کمتر از $x$ باشد، آنگاه $\pi (x)\thicksim {x \over \ln(x)}$.

در حسابان نیز این نماد در تحلیل مجانبی و سری‌های تیلور کاربرد دارد.

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

نماد ${\mathcal {O}}$ معروفترین عضو از مجموعه‌ای از نمادهای دیگری همچون $o$ (کوچک) و ... است که ابداعات پاول باخمن (به آلمانی: Paul Bachmann) و ادموند لانداو (به آلمانی: Edmund Landau‎) بوده اند؛ به همین دلیل به این‌ها نمادهای باخمن-لانداو و یا نمادهای مجانبی (به انگلیسی: asymptotic notations) گفته می‌شود.

تعاریف دقیق

فرض کنید که $f(n)$ تابعی باشد که بخواهیم آن را توصیف کنیم و $g(n)$ نیز یک تابع فرضی ست و همچنین $f$ و $g$ توابع مثبت هستند.

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

نمادهای ${\mathcal {O}}$ و ${\mathcal {\Theta }}$ پرکاربردترین اینها هستند.

O بزرگ

$f\in {\mathcal {O}}(g)\Longleftrightarrow \exists c,n_{0}:\forall n\geqslant n_{0}:0\leqslant f(n)\leqslant cg(n)$

به این معنی که از یک مقدار $n$ خاصی ($n_{0}$) بیشتر، تابع $f$ از ضریبی از تابع $g$ کمتر یا مساوی است.

به عنوان مثال، $n\in {\mathcal {O}}(n^{2})$ و می‌خوانیم «$n$ از اردر $n^{2}$ است» یا «$n$ از اُو $n^{2}$ است» یا «$n^{2}$ کران بالای حدی $n$ است».

به طور رایج، به جای علامت $\in$ از $=$ استفاده می‌شود: $n={\mathcal {O}}(n^{2})$

اما باید دقت کنید که این رابطه تساوی نیست. به عنوان مثال $n={\mathcal {O}}(n^{2})$ و $2n={\mathcal {O}}(n^{2})$ ولی $n\neq 2n$

همچنین ${\mathcal {O}}(n)={\mathcal {O}}(n^{2})$ ولی ${\mathcal {O}}(n^{2})\neq {\mathcal {O}}(n)$

می‌توان ${\mathcal {O}}(g(n))$ را به صورت مجموعهٔ تمام توابعی که از اردر $g$ هستند تصور کرد.

همیشه سعی می‌شود که از ساده‌ترین $g$ ممکن استفاده شود. به عنوان مثال $n={\mathcal {O}}(n^{2})$ و $n={\mathcal {O}}(3n^{2}+2n+1)$ هر دو درست اند ولی اولی ترجیح داده می‌شود.

یک نماد قدیمی به صورت $f\preccurlyeq g$ است. به تفاوت بین علامت $\preccurlyeq$ و $\leqslant$ توجه کنید.

تعریف حدی: $f\preccurlyeq g\Longleftrightarrow \lim _{n\to \infty }{f \over g}<\infty$

o کوچک

$f\in {\mathcal {o}}(g)\Longleftrightarrow \forall c:\exists n_{0}:\forall n\geqslant n_{0}:{0<f(n)<cg(n)}$

به این معنی که از یک مقدار $n$ خاصی ($n_{0}$) بیشتر، تابع $f$ از تابع $g$ و تمام مضارب آن اکیداً کمتر است.

به عنوان مثال، $n={\mathcal {o}}(n^{2})$ و می‌خوانیم «نرخ رشد $n$ از $n^{2}$ کمتر است» یا «$n$ به صورت حدی از $n^{2}$ کوچکتر است».

$n^{2}\neq {\mathcal {o}}(n^{2})$ ولی $n^{2}={\mathcal {O}}(n^{2})$.

تعریف حدّی: $f\prec g\Longleftrightarrow \lim _{n\to \infty }{f \over g}=0$

امگا بزرگ

$f\in {\mathcal {\Omega }}(g)\Longleftrightarrow \exists c,n_{0}:\forall n\geqslant n_{0}:f(n)\geqslant cg(n)\geqslant 0$

به این معنی که از یک مقدار $n$ خاصی ($n_{0}$) بیشتر، تابع $f$ از ضریبی از تابع $g$ بیشتر یا مساوی است.

به عنوان مثال، $n^{2}={\mathcal {\Omega }}(n)$ و می‌خوانیم «$n^{2}$ از امگا $n$ است» یا «$n^{2}$ کران بالای حدی $n$ است».

تعریف حدی: $f\succcurlyeq g\Longleftrightarrow \lim _{n\to \infty }{f \over g}>0$

امگا کوچک

$f\in {\mathcal {\omega }}(g)\Longleftrightarrow \forall c:\exists n_{0}:\forall n\geqslant n_{0}:f(n)>cg(n)>0$

به این معنی که از یک مقدار $n$ خاصی ($n_{0}$) بیشتر، تابع $f$ از تابع $g$ و تمام مضارب آن اکیداً بیشتر است.

به عنوان مثال، $n^{2}={\mathcal {\omega }}(n)$ و می‌خوانیم «نرخ رشد $n^{2}$ از $n$ بیشتر است» یا «$n^{2}$ به صورت حدی از $n$ بزرگتر است».

$n^{2}\neq {\mathcal {\omega }}(n^{2})$ ولی $n^{2}={\mathcal {\Omega }}(n^{2})$.

تعریف حدی: $f\succ g\Longleftrightarrow \lim _{n\to \infty }{f \over g}=\infty$

خاصیت تقارنی ترانهاده با O

$g\in {\mathcal {\Omega }}(f)\Longleftrightarrow g\succcurlyeq f\Longleftrightarrow f\preccurlyeq g\Longleftrightarrow f\in {\mathcal {O}}(g)$

$g\in {\mathcal {\omega }}(f)\Longleftrightarrow g\succ f\Longleftrightarrow f\prec g\Longleftrightarrow f\in {\mathcal {o}}(g)$

تتا

$f\in {\mathcal {\Theta }}(g)\Longleftrightarrow g\in {\mathcal {\Theta }}(f)\Longleftrightarrow \exists c_{1},c_{2},n_{0}:\forall n\geqslant n_{0}:0\leqslant c_{1}g\leqslant f(n)\leqslant c_{2}g(n)$

به این معنی که از یک مقدار $n$ خاصی ($n_{0}$) بیشتر، تابع $f$ در بین ضریب‌هایی از $g$ ساندویچ می‌شود.

به عنوان مثال، $2n={\mathcal {\Theta }}(n)$ و می‌خوانیم «$2n$ از تتا $n$ است» یا «نرخ رشد $2n$ و $n$ یکسان است» یا «$2n$ و $n$ به صورت مجانبی برابر اند».

تعریف حدی: $f\thicksim g\Longleftrightarrow g\thicksim f\Longleftrightarrow \lim _{n\to \infty }{f \over g}=c>0$

با وجود این تعریف در علوم کامپیوتری، تعریف این نماد در ریاضیات کمی متفاوت است: $f\thicksim g\Longleftrightarrow g\thicksim f\Longleftrightarrow \lim _{n\to \infty }{f \over g}=1$

این نماد در تحلیل مجانبی در ریاضیات پرکاربرد است.

قضیه کنوت

$f\in {\mathcal {\Theta }}(g)\Longleftrightarrow g\in {\mathcal {\Theta }}(f)\Longleftrightarrow f\in {\mathcal {O}}(g)\land g\in {\mathcal {O}}(f)$

به این معنی که هم $f$ از اردر $g$ باشد و هم $g$ از اردر $f$ باشد. این قضیه ابداع دونالد کنوت بود و مزیت آن سادگی و قابل‌فهم کردن تعریف است.

به عبارت دیگر اگر نرخ رشد $f$ از $g$ هم بیشتر-مساوی باشد و هم کمتر-مساوی، پس نرخ رشدشان مساوی است.

$f\thicksim g\Longleftrightarrow g\thicksim f\Longleftrightarrow f\preccurlyeq g\preccurlyeq f$

کنوت با این تعریف، نماد O بزرگ را به علوم کامپیوتر معرفی و آن را محبوب کرد.

$\Theta (f)={\mathcal {O}}(f)\cap \Omega (f)$

یک مثال

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

تاریخچه

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

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

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

• پیچیدگی زمانی و حافظه
• تحلیل الگوریتم
• تحلیل مجانبی
• قضیهٔ اعداد اوّل
• آزمون‌های مقایسه‌ای برای همگرایی سری‌ها