نماد O بزرگ

در نظریّهٔ پیچیدگی محاسباتی، نماد O بزرگ (به انگلیسی: Big O notation) یک نماد ریاضیاتی ست که برای توصیف رفتار حدّی یک تابع (وقتی آرگومان‌های آن به بی‌نهایت میل کند) به کار می‌رود.

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

در علوم رایانه، این نماد برای تحلیل الگوریتم‌ها و دسته‌بندی و مقایسهٔ الگوریتم‌های متفاوتِ موجود برای حلّ یک مسئلهٔ خاص به کار می‌رود و نشان‌دهندهٔ رابطهٔ میان «داده‌ها» با «مقدار زمان یا مقدار حافظهٔ مورد نیاز برای پیدا کردن جواب» به کار می‌رود[۱].

در نظریّهٔ تحلیلی اعداد، این نماد برای توصیف میزان دقّت یک تقریب به کار می‌رود. یکی از مثال‌های معروف این موضوع در قضیهٔ اعداد اوّل است: اگر تعداد اعداد اوّل کمتر از باشد، آنگاه یا .

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

به دلیل توصیف رفتار حدّی، علامت O بزرگ به ریاضی‌دان‌ها اجازه می‌دهد که تابع را ساده کنند تا بر روی نرخ رشد آن متمرکز شود؛ بنابراین توابع مختلف با نرخ رشد یکسان می‌توانند دارای یک علامت O مشابه باشند و در نتیجه در یک دسته قرار بگیرند.

نماد O بزرگ معروف‌ترین عضو از مجموعه‌ای از نمادهای دیگری همچون o (کوچک) و ... است که ابداعات پاول باخمن (به آلمانی: Paul Bachmann)[۲] و ادموند لانداو (به آلمانی: Edmund Landau‎)[۳] بوده اند؛ به همین دلیل به این‌ها نمادهای باخمن-لانداو و یا نمادهای مجانبی (به انگلیسی: asymptotic notations) گفته می‌شود.

تعاریف دقیق

فرض کنید که   تابعی باشد که بخواهیم آن را توصیف کنیم و   نیز یک تابع فرضی ست و همچنین   و   توابع مثبت هستند.

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

نمادهای   و   پرکاربردترین اینها هستند.

نماد O بزرگ

 [۱]

به این معنی که از یک مقدار   خاصی ( ) بیشتر، تابع   از ضریبی از تابع   کمتر یا مساوی است.

به عنوان مثال،   و می‌خوانیم «  از اردر   است» یا «  از اُو   است» یا «نرخ رشد   از   کمتر یا مساوی است» یا «  به صورت مجانبی توسّط   (از بالا) محدود می‌شود».

به طور رایج، به جای علامت   از   استفاده می‌شود:  

امّا باید دقّت کنید که این رابطه تساوی نیست. به عنوان مثال   و   ولی  

همچنین   ولی  

می‌توان   را به صورت مجموعهٔ تمام توابعی که از اردر   هستند تصور کرد.

همیشه سعی می‌شود که از ساده‌ترین   ممکن استفاده شود. به عنوان مثال   و   هر دو درست اند ولی اوّلی ترجیح داده می‌شود.[۱]

یک نماد قدیمی که امروزه دیگر استفاده نمی‌شود به این صورت است:  

تعریف حدّی:  [۴]

نماد o کوچک

 [۱]

به این معنی که از یک مقدار   خاصی ( ) بیشتر، تابع   از تابع   و تمام مضارب آن اکیداً کمتر است.

به عنوان مثال،   و می‌خوانیم «نرخ رشد   از   (اکیداً) کمتر است». ولی   (با وجود این که  )

تعریف حدّی:  

امگا بزرگ

 [۱]

به این معنی که از یک مقدار   خاصی ( ) بیشتر، تابع   از ضریبی از تابع   بیشتر یا مساوی است.

به عنوان مثال،   و می‌خوانیم «  از امگا   است» یا «نرخ رشد   از   بیشتر یا مساوی است» یا «  به صورت مجانبی   را (از بالا) محدود می‌کند».

تعریف حدّی:  [۴]

امگا کوچک

 [۱]

به این معنی که از یک مقدار   خاصی ( ) بیشتر، تابع   از تابع   و تمام مضارب آن اکیداً بیشتر است.

به عنوان مثال،   و می‌خوانیم «نرخ رشد   از   (اکیداً) بیشتر است». ولی   (با وجود این که  )

تعریف حدّی:  

خاصیت تقارنی ترانهاده با O

 

 

تتا

 [۱]

به این معنی که از یک مقدار   خاصی ( ) بیشتر، تابع   در بین ضریب‌هایی از   ساندویچ می‌شود.

به عنوان مثال،   و می‌خوانیم «  از تتا   است» یا «نرخ رشد   و   مشابه است» یا «  و   به صورت مجانبی برابر اند».

تعریف حدّی:  [۵]

قضیه کنوت

 [۱]

به این معنی که هم   از اردر   باشد و هم   از اردر   باشد. این قضیه ابداع دونالد کنوت بود و مزیّت آن سادگی و قابل‌فهم کردن تعریف است.

به عبارت دیگر اگر نرخ رشد   از   هم بیشتر-مساوی باشد و هم کمتر-مساوی، پس نرخ رشدشان مساوی است.

 

کنوت با این تعریف، نماد O بزرگ را به علوم کامپیوتر معرّفی و آن را محبوب کرد[۴].

یک مثال

چهار تابع زیر را در نظر بگیرید:

 

 

 

 

رفتار این چهار تابع را طبق نمودارشان بررسی می‌کنیم. در ابتدا به نظر می‌رسد تابع   با توجه به ضریب بزرگتری که دارد مقدارهای بزرگتری نیز داشته باشد که برای   هم همین گونه است.

اما با بزرگ شدن مقدار   رفتار تابع‌ها نیز نسبت به هم متفاوت می‌شود. شکل زیر رفتار توابع را وقتی   است نشان می‌دهد. ملاحظه می‌شود که تابع   به‌تدریج مقدارش از سایر توابع بیشتر می‌شود.

با بزرگتر شدن   وضعیت به این شکل در می‌آید: به‌تدریج تابع   از بقیه توابع بیش‌تر می‌شود.

و برای مقدار بزرگ   داریم:

تابع   کاملاً از بقیه توابع بیشتر می‌شود.

همان طور که دیده شد، چون این تابع از سایر توابع مرتبهٔ بالاتری داشت در نهایت مقدارش از همهٔ آنها بیشتر شد.

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

  یا  و   یا  

  زیرا تابع   همواره حدوداً دوبرابر تابع   است و مرتبهٔ یکسانی دارند.

  یا  

تاریخچه

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

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

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

منابع

  1. ۱٫۰ ۱٫۱ ۱٫۲ ۱٫۳ ۱٫۴ ۱٫۵ ۱٫۶ ۱٫۷ Introduction to Algorithms (CLRS) (3rd edition). به کوشش Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.
  2. Bachmann, Paul (1894). Analytische Zahlentheorie [Analytic Number Theory] (به آلمانی). 2. Leipzig: Teubner.
  3. 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.
  4. ۴٫۰ ۴٫۱ ۴٫۲ 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.
  5. «فصل ۱۰». حسابان (اپوستول) Calculus Vol. 1 (2nd ed.) (Tom M. Apostol).