موضوع مقاله: نماد O بزرگ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نماد O بزرگ | مقدمه: نماد O بزرگ یک نماد ریاضیاتی ست که برای توصیف رفتار حدی یک تابع (وقتی آرگومان‌های آن به بی‌نهایت میل کند) به کار می‌رود. | ## بخش 1: نماد O بزرگ | در علوم رایانه و نظریهٔ پیچیدگی محاسباتی، این نماد برای تحلیل الگوریتم‌ها و دسته‌بندی و مقایسهٔ الگوریتم‌های متفاوتِ موجود برای حل یک مسئلهٔ خاص به کار می‌رود. پیچیدگی محاسباتی نشان‌دهندهٔ رابطهٔ میان «داده‌ها» با «مقدار زمان یا مقدار حافظهٔ مورد نیاز برای پیدا کردن جواب» است و برای توصیف آن از این نماد استفاده می‌شود. یکی از مثال‌های معروف این موضوع در قضیهٔ اعداد اول است: اگر تعداد اعداد اول کمتر از باشد، آنگاه . به دلیل توصیف رفتار حدی، نماد به ریاضی‌دان‌ها اجازه می‌دهد که تابع را ساده کنند تا بر روی نرخ رشد آن متمرکز شود؛ بنابراین توابع مختلف با نرخ رشد یکسان می‌توانند دارای یک نماد مشابه باشند و در نتیجه در یک دسته قرار بگیرند. است که ابداعات پاول باخمن و ادموند لانداو بوده اند؛ به همین دلیل به این‌ها نمادهای باخمن-لانداو و یا نمادهای مجانبی گفته می‌شود. تعاریف دقیق فرض کنید که تابعی باشد که بخواهیم آن را توصیف کنیم و نیز یک تابع فرضی ست و همچنین و توابع مثبت هستند. هر نماد دو تعریف معمول و تعریف حدی دارد (که طبق قضیه‌هایی معادل یکدیگر هستند و به یک مفهوم اشاره دارند). O بزرگ به این معنی که از یک مقدار خاصی بیشتر، تابع از ضریبی از تابع کمتر یا مساوی است. به عنوان مثال، و می‌خوانیم « از اردر است» یا « از اُو است» یا « کران بالای حدی است». | ## بخش 2: نماد O بزرگ | به طور رایج، به جای علامت از استفاده می‌شود: اما باید دقت کنید که این رابطه تساوی نیست. به عنوان مثال و ولی همچنین ولی می‌توان را به صورت مجموعهٔ تمام توابعی که از اردر هستند تصور کرد. تعریف حدی: o کوچک به این معنی که از یک مقدار خاصی بیشتر، تابع از تابع و تمام مضارب آن اکیداً کمتر است. به عنوان مثال، و می‌خوانیم «نرخ رشد از کمتر است» یا « به صورت حدی از کوچکتر است». تعریف حدّی: امگا بزرگ به این معنی که از یک مقدار خاصی بیشتر، تابع از ضریبی از تابع بیشتر یا مساوی است. تعریف حدی: امگا کوچک به این معنی که از یک مقدار خاصی بیشتر، تابع از تابع و تمام مضارب آن اکیداً بیشتر است. به عنوان مثال، و می‌خوانیم «نرخ رشد از بیشتر است» یا « به صورت حدی از بزرگتر است». تعریف حدی: خاصیت تقارنی ترانهاده با O تتا به این معنی که از یک مقدار خاصی بیشتر، تابع در بین ضریب‌هایی از ساندویچ می‌شود. به عنوان مثال، و می‌خوانیم « از تتا است» یا «نرخ رشد و یکسان است» یا « و به صورت مجانبی برابر اند». | ## بخش 3: نماد O بزرگ | تعریف حدی: با وجود این تعریف در علوم کامپیوتری، تعریف این نماد در ریاضیات کمی متفاوت است: این نماد در تحلیل مجانبی در ریاضیات پرکاربرد است. به عبارت دیگر اگر نرخ رشد از هم بیشتر-مساوی باشد و هم کمتر-مساوی، پس نرخ رشدشان مساوی است. یک مثال چهار تابع زیر را در نظر بگیرید: رفتار این چهار تابع را طبق نمودارشان بررسی می‌کنیم. در ابتدا به نظر می‌رسد تابع با توجه به ضریب بزرگتری که دارد مقدارهای بزرگتری نیز داشته باشد که برای هم همین گونه است. وسط|بی‌قاب|773x773پیکسل|نمودار این ۴ تابع وقتی اما با بزرگ شدن مقدار رفتار تابع‌ها نیز نسبت به هم متفاوت می‌شود. وسط|بی‌قاب|802x802پیکسل با بزرگتر شدن وضعیت به این شکل در می‌آید: به‌تدریج تابع از بقیه توابع بیش‌تر می‌شود. وسط|بی‌قاب|774x774پیکسل و برای مقدار بزرگ داریم: تابع کاملاً از بقیه توابع بیشتر می‌شود. همان طور که دیده شد، چون این تابع از سایر توابع مرتبهٔ بالاتری داشت در نهایت مقدارش از همهٔ آنها بیشتر شد. طبق تعاریف بالا می‌توان رابطهٔ این توابع را برحسب نمادگذاری‌های گفته شده بیان کنیم: یا و یا زیرا تابع همواره حدوداً دوبرابر تابع است و مرتبهٔ یکسانی دارند. | ## جمع‌بندی | این علامت در علوم کامپیوتر توسط دانلد کنوت (که علامت‌های مربوطه امگا و تتا را نیز برای اولین بار معرفی کرد) مشهور شد.