نماد O بزرگ کیست؟ توضیح بده.
نماد O بزرگ یک نماد ریاضیاتی ست که برای توصیف رفتار حدی یک تابع (وقتی آرگومان‌های آن به بی‌نهایت میل کند) به کار می‌رود.این نماد (مخفف Order of growth ) اولین بار برای تحلیل سرعت الگوریتم‌های رایانشی ابداع شد و بعدها به حسابان و نظریّهٔ اعداد گسترش یافت.در علوم رایانه و نظریهٔ پیچیدگی محاسباتی، این نماد برای تحلیل الگوریتم‌ها و دسته‌بندی و مقایسهٔ الگوریتم‌های متفاوتِ موجود برای حل یک مسئلهٔ خاص به کار می‌رود. پیچیدگی محاسباتی نشان‌دهندهٔ رابطهٔ میان «"داده‌ها"» با «"مقدار زمان یا مقدار حافظهٔ مورد نیاز برای پیدا کردن جواب"» است و برای توصیف آن از این نماد استفاده می‌شود.در نظریهٔ تحلیلی اعداد، این نماد برای توصیف میزان دقت یک تقریب به کار می‌رود. یکی از مثال‌های معروف این موضوع در قضیهٔ اعداد اول است: اگر formula_1 تعداد اعداد اول کمتر از formula_2 باشد، آنگاه formula_3.در حسابان نیز این نماد در تحلیل مجانبی و سری‌های تیلور کاربرد دارد.به دلیل توصیف رفتار حدی، نماد formula_4 به ریاضی‌دان‌ها اجازه می‌دهد که تابع را ساده کنند تا بر روی نرخ رشد آن متمرکز شود؛ بنابراین توابع مختلف با نرخ رشد یکسان می‌توانند دارای یک نماد formula_4 مشابه باشند و در نتیجه در یک دسته قرار بگیرند.نماد formula_4 معروفترین عضو از مجموعه‌ای از نمادهای دیگری همچون formula_7 (کوچک) و ... است که ابداعات پاول باخمن و ادموند لانداو بوده اند؛ به همین دلیل به این‌ها "نمادهای باخمن-لانداو" و یا نمادهای مجانبی گفته می‌شود.تعاریف دقیق.فرض کنید که formula_8 تابعی باشد که بخواهیم آن را توصیف کنیم و formula_9 نیز یک تابع فرضی ست و همچنین formula_10 و formula_11 توابع مثبت هستند.هر نماد دو تعریف معمول و تعریف حدی دارد (که طبق قضیه‌هایی معادل یکدیگر هستند و به یک مفهوم اشاره دارند).نمادهای formula_4 و formula_13 پرکاربردترین اینها هستند.O بزرگ.formula_14به این معنی که از یک مقدار formula_15 خاصی (formula_16) بیشتر، تابع formula_17 از ضریبی از تابع formula_18 کمتر یا مساوی است.به عنوان مثال، formula_19 و می‌خوانیم «formula_15 از اردر formula_21 است» یا «formula_15 از اُو formula_21 است» یا «formula_21 کران بالای حدی formula_15 است».به طور رایج، به جای علامت formula_26 از formula_27 استفاده می‌شود: formula_28اما باید دقت کنید که این رابطه تساوی نیست. به عنوان مثال formula_28 و formula_30 ولی formula_31همچنین formula_32 ولی formula_33می‌توان formula_34 را به صورت مجموعهٔ تمام توابعی که از اردر formula_18 هستند تصور کرد.همیشه سعی می‌شود که از ساده‌ترین formula_11 ممکن استفاده شود. به عنوان مثال formula_28 و formula_38 هر دو درست اند ولی اولی ترجیح داده می‌شود.یک نماد قدیمی به صورت formula_39 است. به تفاوت بین علامت formula_40 و formula_41 توجه کنید.تعریف حدی: formula_42o کوچک.formula_43به این معنی که از یک مقدار formula_15 خاصی (formula_16) بیشتر، تابع formula_17 از تابع formula_18 و تمام مضارب آن اکیداً کمتر است.به عنوان مثال، formula_48 و می‌خوانیم «نرخ رشد formula_15 از formula_21 کمتر است» یا «formula_15 به صورت حدی از formula_21 کوچکتر است».formula_53 ولی formula_54.تعریف حدّی: formula_55امگا بزرگ.formula_56به این معنی که از یک مقدار formula_15 خاصی (formula_16) بیشتر، تابع formula_17 از ضریبی از تابع formula_18 بیشتر یا مساوی است.به عنوان مثال، formula_61 و می‌خوانیم «formula_21 از امگا formula_15 است» یا «formula_21 کران بالای حدی formula_15 است».تعریف حدی: formula_66امگا کوچک.formula_67به این معنی که از یک مقدار formula_15 خاصی (formula_16) بیشتر، تابع formula_17 از تابع formula_18 و تمام مضارب آن اکیداً بیشتر است.به عنوان مثال، formula_72 و می‌خوانیم «نرخ رشد formula_21 از formula_15 بیشتر است» یا «formula_21 به صورت حدی از formula_15 بزرگتر است».formula_77 ولی formula_78.تعریف حدی: formula_79خاصیت تقارنی ترانهاده با O.formula_80formula_81تتا.formula_82به این معنی که از یک مقدار formula_15 خاصی (formula_16) بیشتر، تابع formula_17 در بین ضریب‌هایی از formula_18 ساندویچ می‌شود.به عنوان مثال، formula_87 و می‌خوانیم «formula_88 از تتا formula_15 است» یا «نرخ رشد formula_88 و formula_15 یکسان است» یا «formula_88 و formula_15 به صورت مجانبی برابر اند».تعریف حدی: formula_94با وجود این تعریف در علوم کامپیوتری، تعریف این نماد در ریاضیات کمی متفاوت است: formula_95این نماد در تحلیل مجانبی در ریاضیات پرکاربرد است.قضیه کنوت.formula_96به این معنی که هم formula_17 از اردر formula_18 باشد و هم formula_18 از اردر formula_17 باشد. این قضیه ابداع دونالد کنوت بود و مزیت آن سادگی و قابل‌فهم کردن تعریف است.به عبارت دیگر اگر نرخ رشد formula_17 از formula_18 هم بیشتر-مساوی باشد و هم کمتر-مساوی، پس نرخ رشدشان مساوی است.formula_103کنوت با این تعریف، نماد O بزرگ را به علوم کامپیوتر معرفی و آن را محبوب کرد.formula_104یک مثال.چهار تابع زیر را در نظر بگیرید:formula_105formula_106formula_107formula_108رفتار این چهار تابع را طبق نمودارشان بررسی می‌کنیم. در ابتدا به نظر می‌رسد تابع formula_17 با توجه به ضریب بزرگتری که دارد مقدارهای بزرگتری نیز داشته باشد که برای formula_110 هم همین گونه است.اما با بزرگ شدن مقدار formula_15 رفتار تابع‌ها نیز نسبت به هم متفاوت می‌شود. شکل زیر رفتار توابع را وقتی formula_112 است نشان می‌دهد. ملاحظه می‌شود که تابع formula_18 به‌تدریج مقدارش از سایر توابع بیشتر می‌شود.با بزرگتر شدن formula_15 وضعیت به این شکل در می‌آید: به‌تدریج تابع formula_115 از بقیه توابع بیش‌تر می‌شود.و برای مقدار بزرگ formula_15 داریم:تابع formula_115 کاملاً از بقیه توابع بیشتر می‌شود.همان طور که دیده شد، چون این تابع از سایر توابع مرتبهٔ بالاتری داشت در نهایت مقدارش از همهٔ آنها بیشتر شد.طبق تعاریف بالا می‌توان رابطهٔ این توابع را برحسب نمادگذاری‌های گفته شده بیان کنیم:formula_118 یا formula_119و formula_120 یا formula_121formula_122 زیرا تابع formula_18 همواره حدوداً دوبرابر تابع formula_124 است و مرتبهٔ یکسانی دارند.formula_125 یا formula_126تاریخچه.علامت O بزرگ اولین بار توسط متخصص اعداد Paul Bachmann در سال ۱۸۹۴، در جلد دوم کتاب "Analytische Zahlentheorie" معرفی شد (که جلد اولش در سال ۱۸۹۲ چاپ شده و شامل این علامت نبود). این علامت در کارهای نظریه اعداد توسط ادموند لانداو متداول شد و به همین خاطر گاهی از آن به نام Landau symbol یاد می‌شود.این علامت در علوم کامپیوتر توسط دانلد کنوت (که علامت‌های مربوطه امگا و تتا را نیز برای اولین بار معرفی کرد) مشهور شد. او هم چنین متذکر شد که علامت امگا توسط Hardy و Littlewood تحت معنی اندکی متفاوت قبلاً تعریف شده بوده‌است.