نمایش مبدأ برای نماد O بزرگ

'''نماد O بزرگ''' {{انگلیسی|Big O notation}} یک نماد ریاضیاتی ست که برای توصیف رفتار [[حد (ریاضی)|حدی]] یک [[تابع (ریاضیات)|تابع]] (وقتی [[شناسه تابع|آرگومان‌های]] آن به [[بی‌نهایت]] میل کند) به کار می‌رود.

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

در [[علوم رایانه]] و [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]]، این نماد برای [[تحلیل الگوریتم‌ها]] و دسته‌بندی و مقایسهٔ الگوریتم‌های متفاوتِ موجود برای حل یک مسئلهٔ خاص به کار می‌رود. [[پیچیدگی محاسباتی]] نشان‌دهندهٔ رابطهٔ میان «[[داده|''داده‌ها'']]» با «''مقدار [[پیچیدگی زمانی|زمان]] یا مقدار [[حافظه دسترسی تصادفی|حافظهٔ]] مورد نیاز برای پیدا کردن جواب''» است و برای توصیف آن از این نماد استفاده می‌شود.<ref name=":02">{{یادکرد کتاب|عنوان=Introduction to Algorithms (CLRS) (3rd edition)|شناسه=978-0262033848|کوشش=Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein}}</ref>

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

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

به دلیل توصیف رفتار [[حد (ریاضی)|حدی]]، نماد <math>\mathcal O</math> به ریاضی‌دان‌ها اجازه می‌دهد که [[تابع (ریاضیات)|تابع]] را ساده کنند تا بر روی نرخ رشد آن متمرکز شود؛ بنابراین توابع مختلف با نرخ رشد یکسان می‌توانند دارای یک نماد <math>\mathcal O</math> مشابه باشند و در نتیجه در یک دسته قرار بگیرند.

نماد <math>\mathcal O</math> معروفترین عضو از مجموعه‌ای از نمادهای دیگری همچون <math>o</math> (کوچک) و ... است که ابداعات پاول باخمن {{به آلمانی|Paul Bachmann}}<ref name="Bachmann2">{{cite book|first=Paul|last=Bachmann|author-link=Paul Bachmann|title=Analytische Zahlentheorie|trans-title=Analytic Number Theory|language=de|volume=2|location=Leipzig|publisher=Teubner|date=1894|url=https://archive.org/stream/dieanalytischeza00bachuoft#page/402/mode/2up}}</ref> و [[ادموند لانداو]] {{به آلمانی|Edmund Landau‎}}<ref name="Landau2">{{cite book|first=Edmund|last=Landau|author-link=Edmund Landau|title=Handbuch der Lehre von der Verteilung der Primzahlen|publisher=B. G. Teubner|date=1909|location=Leipzig|trans-title=Handbook on the theory of the distribution of the primes|language=de|page=883|url=https://archive.org/details/handbuchderlehre01landuoft}}</ref> بوده اند؛ به همین دلیل به این‌ها ''نمادهای باخمن-لانداو'' و یا '''نمادهای مجانبی''' {{به انگلیسی|asymptotic notations}} گفته می‌شود.

== تعاریف دقیق ==
فرض کنید که <math> f(n) </math> [[تابع (ریاضیات)|تابعی]] باشد که بخواهیم آن را توصیف کنیم و <math> g(n) </math> نیز یک [[تابع (ریاضیات)|تابع]] فرضی ست و همچنین <math> f </math> و <math> g </math> توابع مثبت هستند.

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

نمادهای <math>\mathcal O</math> و <math>\mathcal \Theta</math> پرکاربردترین اینها هستند.

=== O بزرگ ===
<math>f \in \mathcal O(g) \Longleftrightarrow \exists c, n_0: \forall n \geqslant n_0: 0 \leqslant f(n) \leqslant cg(n)</math><ref name=":02" />

به این معنی که از یک مقدار <math>n</math> خاصی (<math>n_0</math>) بیشتر، [[تابع (ریاضیات)|تابع]] <math>f</math> از ضریبی از [[تابع (ریاضیات)|تابع]] <math>g</math> کمتر یا مساوی است.

به عنوان مثال، <math>n \in \mathcal O(n^2)</math> و می‌خوانیم «<math>n</math> از اردر <math>n^2</math> است» یا «<math>n</math> از اُو <math>n^2</math> است» یا «<math>n^2</math> کران بالای حدی <math>n</math> است».<ref>{{یادکرد کتاب|عنوان=مقدمه‌ای بر الگوریتم‌ها (ویراست سوم)|کوشش=توماس کورمن، چارلز لیزرسون، رونالد ریوست و کلیفورد استین|شناسه=۹۷۸-۹۶۴-۴۱۰-۲۵۸-۵|دیگران=ترجمه مهندس دهقان طرزه}}</ref>

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

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

همچنین <math>\mathcal O(n) = \mathcal O(n^2)</math> ولی <math>\mathcal O(n^2) \neq \mathcal O(n)</math>

می‌توان <math>\mathcal O(g(n))</math> را به صورت [[مجموعه (ریاضیات)|مجموعهٔ]] تمام [[تابع (ریاضیات)|توابعی]] که از اردر <math>g</math> هستند تصور کرد.

همیشه سعی می‌شود که از ساده‌ترین <math> g </math> ممکن استفاده شود. به عنوان مثال <math>n = \mathcal O(n^2)</math> و <math>n = \mathcal O(3n^2 + 2n + 1)</math> هر دو درست اند ولی اولی ترجیح داده می‌شود.<ref name=":02" />

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

تعریف حدی: <math>f \preccurlyeq g \Longleftrightarrow \lim_{n \to \infty} {f \over g} < \infty</math><ref name="knuth22">{{cite journal|last=Knuth|first=Donald|date=April–June 1976|title=Big Omicron and big Omega and big Theta|url=http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf|journal=SIGACT News|volume=8|issue=2|pages=18–24|doi=10.1145/1008328.1008329|s2cid=5230246|access-date=۲۸ سپتامبر ۲۰۲۱|archive-date=۳۰ نوامبر ۲۰۲۱|archive-url=https://web.archive.org/web/20211130005215/https://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf|url-status=dead}}</ref>

==== o کوچک ====
<math>f \in \mathcal o(g) \Longleftrightarrow \forall c: \exists n_0: \forall n \geqslant n_0: {0 < f(n) < cg(n)}</math><ref name=":02" />

به این معنی که از یک مقدار <math>n</math> خاصی (<math>n_0</math>) بیشتر، [[تابع (ریاضیات)|تابع]] <math>f</math> از [[تابع (ریاضیات)|تابع]] <math>g</math> و تمام مضارب آن اکیداً کمتر است.

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

<math>n^2 \neq \mathcal o(n^2)</math> ولی <math>n^2 = \mathcal O(n^2)</math>.

تعریف حدّی: <math>f\prec g \Longleftrightarrow \lim_{n \to \infty} {f \over g} = 0</math>

=== امگا بزرگ ===
<math>f \in \mathcal\Omega(g) \Longleftrightarrow \exists c, n_0: \forall n \geqslant n_0: f(n) \geqslant cg(n) \geqslant 0</math><ref name=":02" />

به این معنی که از یک مقدار <math>n</math> خاصی (<math>n_0</math>) بیشتر، [[تابع (ریاضیات)|تابع]] <math>f</math> از ضریبی از [[تابع (ریاضیات)|تابع]] <math>g</math> بیشتر یا مساوی است.

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

تعریف حدی: <math>f \succcurlyeq g \Longleftrightarrow \lim_{n \to \infty} {f \over g} > 0</math><ref name="knuth22" />

==== امگا کوچک ====
<math>f \in \mathcal\omega(g) \Longleftrightarrow \forall c: \exists n_0: \forall n \geqslant n_0: f(n) > cg(n) > 0</math><ref name=":02" />

به این معنی که از یک مقدار <math>n</math> خاصی (<math>n_0</math>) بیشتر، [[تابع (ریاضیات)|تابع]] <math>f</math> از [[تابع (ریاضیات)|تابع]] <math>g</math> و تمام مضارب آن اکیداً بیشتر است.

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

<math>n^2 \neq \mathcal\omega(n^2)</math> ولی <math>n^2 = \mathcal\Omega(n^2)</math>.

تعریف حدی: <math>f \succ g \Longleftrightarrow \lim_{n \to \infty} {f \over g} = \infty</math>

==== خاصیت تقارنی ترانهاده با O ====
<math>g \in \mathcal\Omega(f) \Longleftrightarrow g \succcurlyeq f \Longleftrightarrow f \preccurlyeq g  \Longleftrightarrow f \in \mathcal O(g)</math>

<math>g \in \mathcal\omega(f) \Longleftrightarrow g \succ f \Longleftrightarrow f \prec g  \Longleftrightarrow f \in \mathcal o(g)</math>

=== تتا ===
<math>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)</math><ref name=":02" />

به این معنی که از یک مقدار <math>n</math> خاصی (<math>n_0</math>) بیشتر، [[تابع (ریاضیات)|تابع]] <math>f</math> در بین ضریب‌هایی از <math>g</math> [[قضیه فشردگی|ساندویچ]] می‌شود.

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

تعریف حدی: <math>f \thicksim g \Longleftrightarrow g \thicksim f \Longleftrightarrow \lim_{n \to \infty} {f \over g} = c > 0</math><ref name=":02" />

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

این نماد در [[تحلیل مجانبی]] در ریاضیات پرکاربرد است.<ref name=":12">{{یادکرد کتاب|عنوان=Calculus Vol. 1 (2nd ed.)|شناسه=978-0-471-00005-1|کوشش=Tom M. Apostol}}</ref>

==== قضیه کنوت ====
<math>f \in \mathcal\Theta(g) \Longleftrightarrow g \in \mathcal\Theta(f) \Longleftrightarrow f \in \mathcal O(g) \and g \in \mathcal O(f)</math><ref name=":02" />

به این معنی که هم <math>f</math> از اردر <math>g</math> باشد و هم <math>g</math> از اردر <math>f</math> باشد. این قضیه ابداع [[دانلد کنوت|دونالد کنوت]] بود و مزیت آن سادگی و قابل‌فهم کردن تعریف است.

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

<math>f \thicksim g \Longleftrightarrow g \thicksim f \Longleftrightarrow f \preccurlyeq g \preccurlyeq f </math>

کنوت با این تعریف، نماد O بزرگ را به علوم کامپیوتر معرفی و آن را محبوب کرد.<ref name="knuth22" />

<math>\Theta(f) = \mathcal O(f) \cap \Omega (f)</math>

== یک مثال ==
چهار [[تابع (ریاضیات)|تابع]] زیر را در نظر بگیرید:

<math>f(n) = 1000n^2 + 20n + 16</math>

<math>g(n)=2n^3 + 100n^{\tfrac{4}{3}} + 56</math>

<math>h(n)=n^3 - \frac{1}{2}n^2 + \frac{1}{3}n</math>

<math>i(n) = \frac{1}{1000}n^4</math>

رفتار این چهار [[تابع (ریاضیات)|تابع]] را طبق نمودارشان بررسی می‌کنیم. در ابتدا به نظر می‌رسد [[تابع (ریاضیات)|تابع]] <math>f</math> با توجه به ضریب بزرگتری که دارد مقدارهای بزرگتری نیز داشته باشد که برای <math>n \le 100</math> هم همین گونه است.
[[پرونده:نمودار_۱.jpg|وسط|بی‌قاب|773x773پیکسل|نمودار این ۴ تابع وقتی <math>n \le 100</math>]]
اما با بزرگ شدن مقدار <math>n</math> رفتار [[تابع (ریاضیات)|تابع‌ها]] نیز نسبت به هم متفاوت می‌شود. شکل زیر رفتار [[تابع (ریاضیات)|توابع]] را وقتی <math>n \le 1000</math> است نشان می‌دهد. ملاحظه می‌شود که [[تابع (ریاضیات)|تابع]] <math>g</math> به‌تدریج مقدارش از سایر [[تابع (ریاضیات)|توابع]] بیشتر می‌شود.
[[پرونده:نمودار۲.jpg|وسط|بی‌قاب|802x802پیکسل]]
با بزرگتر شدن <math>n</math> وضعیت به این شکل در می‌آید: به‌تدریج [[تابع (ریاضیات)|تابع]] <math>i</math> از بقیه [[تابع (ریاضیات)|توابع]] بیش‌تر می‌شود.
[[پرونده:نمودار_۳.jpg|وسط|بی‌قاب|774x774پیکسل]]
و برای مقدار بزرگ <math>n</math> داریم:

[[تابع (ریاضیات)|تابع]] <math>i</math> کاملاً از بقیه [[تابع (ریاضیات)|توابع]] بیشتر می‌شود.

همان طور که دیده شد، چون این [[تابع (ریاضیات)|تابع]] از سایر توابع مرتبهٔ بالاتری داشت در نهایت مقدارش از همهٔ آنها بیشتر شد.

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

<math>f(n) = \mathcal O(g(n))</math> یا <math>f(n) = o(g(n))</math>و <math>g(n) = \Omega (f(n))</math> یا <math>g(n) = \omega(f(n))</math>

<math>g(n) = \Theta(h(n))</math> زیرا [[تابع (ریاضیات)|تابع]] <math>g</math> همواره حدوداً دوبرابر [[تابع (ریاضیات)|تابع]] <math>h</math> است و مرتبهٔ یکسانی دارند.

<math>h(n) = \mathcal O(i(n))</math> یا <math>h(n) = o(i(n))</math>

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

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

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

* [[پیچیدگی زمانی|پیچیدگی زمانی و حافظه]]
* [[تحلیل الگوریتم‌ها|تحلیل الگوریتم]]
* [[تحلیل مجانبی]]
* [[قضیه اعداد اول|قضیهٔ اعداد اوّل]]
* [[سری (ریاضیات)#%D8%A2%D8%B2%D9%85%D9%88%D9%86 %D9%85%D9%82%D8%A7%DB%8C%D8%B3%D9%87%25E2%2580%258C%D8%A7%DB%8C %D8%A7%D9%8F%D8%B1%D8%AF%D8%B1|آزمون‌های مقایسه‌ای برای همگرایی سری‌ها]]

== منابع ==
{{پانویس}}

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