نماد O بزرگ
در نظریّهٔ پیچیدگی محاسباتی، نماد O بزرگ یک نماد ریاضیاتی ست که برای توصیف رفتار حدّی یک تابع (وقتی آرگومان‌های آن به بی‌نهایت میل کند) به کار می‌رود.
این نماد اوّلین بار (به عنوان مخفّف Order of growth ) برای تحلیل سرعت الگوریتم‌های رایانشی ابداع شد و بعدها به حسابان و نظریّهٔ اعداد گسترش یافت.
در علوم رایانه، این نماد برای تحلیل الگوریتم‌ها و دسته‌بندی و مقایسهٔ الگوریتم‌های متفاوتِ موجود برای حلّ یک مسئلهٔ خاص به کار می‌رود و نشان‌دهندهٔ رابطهٔ میان «"داده‌ها"» با «"مقدار زمان یا مقدار حافظهٔ مورد نیاز برای پیدا کردن جواب"» به کار می‌رود.
در نظریّهٔ تحلیلی اعداد، این نماد برای توصیف میزان دقّت یک تقریب به کار می‌رود. یکی از مثال‌های معروف این موضوع در قضیهٔ اعداد اوّل است: اگر formula_1 تعداد اعداد اوّل کمتر از formula_2 باشد، آنگاه formula_3 یا formula_4.
در حسابان نیز این نماد در تحلیل مجانبی و سری‌های تیلور کاربرد دارد.
به دلیل توصیف رفتار حدّی، علامت O بزرگ به ریاضی‌دان‌ها اجازه می‌دهد که تابع را ساده کنند تا بر روی نرخ رشد آن متمرکز شود؛ بنابراین توابع مختلف با نرخ رشد یکسان می‌توانند دارای یک علامت O مشابه باشند و در نتیجه در یک دسته قرار بگیرند.
نماد O بزرگ معروف‌ترین عضو از مجموعه‌ای از نمادهای دیگری همچون o (کوچک) و ... است که ابداعات پاول باخمن و ادموند لانداو بوده اند؛ به همین دلیل به این‌ها "نمادهای باخمن-لانداو" و یا "نمادهای مجانبی" گفته می‌شود.
فرض کنید که formula_5 تابعی باشد که بخواهیم آن را توصیف کنیم و formula_6 نیز یک تابع فرضی ست و همچنین formula_7 و formula_8 توابع مثبت هستند.
هر نماد دو تعریف معمول و تعریف حدّی دارد (که طبق قضیه‌هایی معادل یکدیگر هستند و به یک مفهوم اشاره دارند).
نمادهای formula_9 و formula_10 پرکاربردترین اینها هستند.
formula_11
به این معنی که از یک مقدار formula_12 خاصی (formula_13) بیشتر، تابع formula_14 از ضریبی از تابع formula_15 کمتر یا مساوی است.
به عنوان مثال، formula_16 و می‌خوانیم «formula_12 از اردر formula_18 است» یا «formula_12 از اُو formula_18 است» یا «نرخ رشد formula_12 از formula_18 کمتر یا مساوی است» یا «formula_12 به صورت مجانبی توسّط formula_18 (از بالا) محدود می‌شود».
به طور رایج، به جای علامت formula_25 از formula_26 استفاده می‌شود: formula_27
امّا باید دقّت کنید که این رابطه تساوی نیست. به عنوان مثال formula_27 و formula_29 ولی formula_30
همچنین formula_31 ولی formula_32
می‌توان formula_33 را به صورت مجموعهٔ تمام توابعی که از اردر formula_15 هستند تصور کرد.
همیشه سعی می‌شود که از ساده‌ترین formula_8 ممکن استفاده شود. به عنوان مثال formula_27 و formula_37 هر دو درست اند ولی اوّلی ترجیح داده می‌شود.
یک نماد قدیمی که امروزه دیگر استفاده نمی‌شود به این صورت است: formula_38
تعریف حدّی: formula_39
formula_40
به این معنی که از یک مقدار formula_12 خاصی (formula_13) بیشتر، تابع formula_14 از تابع formula_15 و تمام مضارب آن اکیداً کمتر است.
به عنوان مثال، formula_45 و می‌خوانیم «نرخ رشد formula_12 از formula_18 (اکیداً) کمتر است». ولی formula_48 (با وجود این که formula_49)
تعریف حدّی: formula_50
formula_51
به این معنی که از یک مقدار formula_12 خاصی (formula_13) بیشتر، تابع formula_14 از ضریبی از تابع formula_15 بیشتر یا مساوی است.
به عنوان مثال، formula_56 و می‌خوانیم «formula_18 از امگا formula_12 است» یا «نرخ رشد formula_18 از formula_12 بیشتر یا مساوی است» یا «formula_18 به صورت مجانبی formula_12 را (از بالا) محدود می‌کند».
تعریف حدّی: formula_63
formula_64
به این معنی که از یک مقدار formula_12 خاصی (formula_13) بیشتر، تابع formula_14 از تابع formula_15 و تمام مضارب آن اکیداً بیشتر است.
به عنوان مثال، formula_69 و می‌خوانیم «نرخ رشد formula_18 از formula_12 (اکیداً) بیشتر است». ولی formula_72 (با وجود این که formula_73)
تعریف حدّی: formula_74
formula_75
formula_76
formula_77
به این معنی که از یک مقدار formula_12 خاصی (formula_13) بیشتر، تابع formula_14 در بین ضریب‌هایی از formula_15 ساندویچ می‌شود.
به عنوان مثال، formula_82 و می‌خوانیم «formula_83 از تتا formula_12 است» یا «نرخ رشد formula_83 و formula_12 مشابه است» یا «formula_83 و formula_12 به صورت مجانبی برابر اند».
تعریف حدّی: formula_89
formula_90
به این معنی که هم formula_14 از اردر formula_15 باشد و هم formula_15 از اردر formula_14 باشد. این قضیه ابداع دونالد کنوت بود و مزیّت آن سادگی و قابل‌فهم کردن تعریف است.
به عبارت دیگر اگر نرخ رشد formula_14 از formula_15 هم بیشتر-مساوی باشد و هم کمتر-مساوی، پس نرخ رشدشان مساوی است.
formula_97
کنوت با این تعریف، نماد O بزرگ را به علوم کامپیوتر معرّفی و آن را محبوب کرد.
چهار تابع زیر را در نظر بگیرید:
formula_98
formula_99
formula_100
formula_101
رفتار این چهار تابع را طبق نمودارشان بررسی می‌کنیم. در ابتدا به نظر می‌رسد تابع formula_14 با توجه به ضریب بزرگتری که دارد مقدارهای بزرگتری نیز داشته باشد که برای formula_103 هم همین گونه است.
اما با بزرگ شدن مقدار formula_12 رفتار تابع‌ها نیز نسبت به هم متفاوت می‌شود. شکل زیر رفتار توابع را وقتی formula_105 است نشان می‌دهد. ملاحظه می‌شود که تابع formula_15 به‌تدریج مقدارش از سایر توابع بیشتر می‌شود.
با بزرگتر شدن formula_12 وضعیت به این شکل در می‌آید: به‌تدریج تابع formula_108 از بقیه توابع بیش‌تر می‌شود.
و برای مقدار بزرگ formula_12 داریم:
تابع formula_108 کاملاً از بقیه توابع بیشتر می‌شود.
همان طور که دیده شد، چون این تابع از سایر توابع مرتبهٔ بالاتری داشت در نهایت مقدارش از همهٔ آنها بیشتر شد.
طبق تعاریف بالا می‌توان رابطهٔ این توابع را برحسب نمادگذاری‌های گفته شده بیان کنیم:
formula_111 یا formula_112و formula_113 یا formula_114
formula_115 زیرا تابع formula_15 همواره حدوداً دوبرابر تابع formula_117 است و مرتبهٔ یکسانی دارند.
formula_118 یا formula_119
علامت O بزرگ اولین بار توسط متخصص اعداد Paul Bachmann در سال ۱۸۹۴، در جلد دوم کتاب "Analytische Zahlentheorie" معرفی شد (که جلد اولش در سال ۱۸۹۲ چاپ شده و شامل این علامت نبود). این علامت در کارهای نظریه اعداد توسط ادموند لانداو متداول شد و به همین خاطر گاهی از آن به نام Landau symbol یاد می‌شود.
این علامت در علوم کامپیوتر توسط دانلد کنوت (که علامت‌های مربوطه امگا و تتا را نیز برای اولین بار معرفی کرد) مشهور شد. او هم چنین متذکر شد که علامت امگا توسط Hardy و Littlewood تحت معنی اندکی متفاوت قبلاً تعریف شده بوده‌است.