نماد O بزرگ
نماد O بزرگ (به انگلیسی: Big O notation) یک نماد ریاضیاتی ست که برای توصیف رفتار حدی یک تابع (وقتی آرگومانهای آن به بینهایت میل کند) به کار میرود.
این نماد (مخفف Order of growth (به فارسی: مرتبهٔ رشد)) اولین بار برای تحلیل سرعت الگوریتمهای رایانشی ابداع شد و بعدها به حسابان و نظریّهٔ اعداد گسترش یافت.
در علوم رایانه و نظریهٔ پیچیدگی محاسباتی، این نماد برای تحلیل الگوریتمها و دستهبندی و مقایسهٔ الگوریتمهای متفاوتِ موجود برای حل یک مسئلهٔ خاص به کار میرود. پیچیدگی محاسباتی نشاندهندهٔ رابطهٔ میان «دادهها» با «مقدار زمان یا مقدار حافظهٔ مورد نیاز برای پیدا کردن جواب» است و برای توصیف آن از این نماد استفاده میشود.
در نظریهٔ تحلیلی اعداد، این نماد برای توصیف میزان دقت یک تقریب به کار میرود. یکی از مثالهای معروف این موضوع در قضیهٔ اعداد اول است: اگر
در حسابان نیز این نماد در تحلیل مجانبی و سریهای تیلور کاربرد دارد.
به دلیل توصیف رفتار حدی، نماد
نماد
تعاریف دقیق
فرض کنید که
هر نماد دو تعریف معمول و تعریف حدی دارد (که طبق قضیههایی معادل یکدیگر هستند و به یک مفهوم اشاره دارند).
نمادهای
O بزرگ
به این معنی که از یک مقدار
به عنوان مثال،
به طور رایج، به جای علامت
اما باید دقت کنید که این رابطه تساوی نیست. به عنوان مثال
همچنین
میتوان
همیشه سعی میشود که از سادهترین
یک نماد قدیمی به صورت
تعریف حدی:
o کوچک
به این معنی که از یک مقدار
به عنوان مثال،
تعریف حدّی:
امگا بزرگ
به این معنی که از یک مقدار
به عنوان مثال،
تعریف حدی:
امگا کوچک
به این معنی که از یک مقدار
به عنوان مثال،
تعریف حدی:
خاصیت تقارنی ترانهاده با O
تتا
به این معنی که از یک مقدار
به عنوان مثال،
تعریف حدی:
با وجود این تعریف در علوم کامپیوتری، تعریف این نماد در ریاضیات کمی متفاوت است:
این نماد در تحلیل مجانبی در ریاضیات پرکاربرد است.
قضیه کنوت
به این معنی که هم
به عبارت دیگر اگر نرخ رشد
کنوت با این تعریف، نماد O بزرگ را به علوم کامپیوتر معرفی و آن را محبوب کرد.
یک مثال
چهار تابع زیر را در نظر بگیرید:
رفتار این چهار تابع را طبق نمودارشان بررسی میکنیم. در ابتدا به نظر میرسد تابع
اما با بزرگ شدن مقدار
با بزرگتر شدن
و برای مقدار بزرگ
تابع
همان طور که دیده شد، چون این تابع از سایر توابع مرتبهٔ بالاتری داشت در نهایت مقدارش از همهٔ آنها بیشتر شد.
طبق تعاریف بالا میتوان رابطهٔ این توابع را برحسب نمادگذاریهای گفته شده بیان کنیم:
تاریخچه
علامت O بزرگ اولین بار توسط متخصص اعداد Paul Bachmann در سال ۱۸۹۴، در جلد دوم کتاب Analytische Zahlentheorie معرفی شد (که جلد اولش در سال ۱۸۹۲ چاپ شده و شامل این علامت نبود). این علامت در کارهای نظریه اعداد توسط ادموند لانداو متداول شد و به همین خاطر گاهی از آن به نام Landau symbol یاد میشود.
این علامت در علوم کامپیوتر توسط دانلد کنوت (که علامتهای مربوطه امگا و تتا را نیز برای اولین بار معرفی کرد) مشهور شد. او هم چنین متذکر شد که علامت امگا توسط Hardy و Littlewood تحت معنی اندکی متفاوت قبلاً تعریف شده بودهاست.
جستارهای وابسته
- پیچیدگی زمانی و حافظه
- تحلیل الگوریتم
- تحلیل مجانبی
- قضیهٔ اعداد اوّل
- آزمونهای مقایسهای برای همگرایی سریها
منابع
- ↑ Introduction to Algorithms (CLRS) (3rd edition). به کوشش Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.
- ↑ Bachmann, Paul (1894). Analytische Zahlentheorie [Analytic Number Theory] (به آلمانی). Vol. 2. Leipzig: Teubner.
- ↑ Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Handbook on the theory of the distribution of the primes] (به آلمانی). Leipzig: B. G. Teubner. p. 883.
- ↑ مقدمهای بر الگوریتمها (ویراست سوم). به کوشش توماس کورمن، چارلز لیزرسون، رونالد ریوست و کلیفورد استین. ترجمه مهندس دهقان طرزه.
- ↑ Knuth, Donald (April–June 1976). "Big Omicron and big Omega and big Theta" (PDF). SIGACT News. 8 (2): 18–24. doi:10.1145/1008328.1008329. S2CID 5230246. Archived from the original (PDF) on 30 November 2021. Retrieved 28 September 2021.
- ↑ Calculus Vol. 1 (2nd ed.). به کوشش Tom M. Apostol.