نماد O بزرگ

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

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

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

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

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

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

نماد \mathcal O معروفترین عضو از مجموعه‌ای از نمادهای دیگری همچون o (کوچک) و ... است که ابداعات پاول باخمن  و ادموند لانداو  بوده اند؛ به همین دلیل به این‌ها *نمادهای باخمن-لانداو* و یا **نمادهای مجانبی**  گفته می‌شود.

## تعاریف دقیق
فرض کنید که  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} 

#### o کوچک
f \in \mathcal o(g) \Longleftrightarrow \forall c: \exists n_0: \forall n \geqslant n_0: {0 

به این معنی که از یک مقدار 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) \and 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 \le 100 هم همین گونه است.
وسط|بی‌قاب|773x773پیکسل|نمودار این ۴ تابع وقتی <math>n \le 100</math>
اما با بزرگ شدن مقدار n رفتار تابع‌ها نیز نسبت به هم متفاوت می‌شود. شکل زیر رفتار توابع را وقتی n \le 1000 است نشان می‌دهد. ملاحظه می‌شود که تابع g به‌تدریج مقدارش از سایر توابع بیشتر می‌شود.
وسط|بی‌قاب|802x802پیکسل
با بزرگتر شدن n وضعیت به این شکل در می‌آید: به‌تدریج تابع i از بقیه توابع بیش‌تر می‌شود.
وسط|بی‌قاب|774x774پیکسل
و برای مقدار بزرگ 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 تحت معنی اندکی متفاوت قبلاً تعریف شده بوده‌است.

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

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

## منابع

رده:آنالیز تقریبی
رده:تحلیل الگوریتم‌ها
رده:محاسبات عددی
رده:نشانه‌گذاری ریاضی