نماد O بزرگ: تفاوت میان نسخه‌ها

 

وقتی تابعی را با استفاده از علامت O بزرگ توصیف می‌کنیم معمولاً تنها یک کران بالا برای نرخ رشد آن تابع فراهم می‌کنیم. علامت‌های مرتبط دیگر برای توصیف توابع عبارتند از: [[o]], [[Ω]], [[ω]], [[Θ]].

فرض کنید (''f'' (''x'') ,''g'' (''x'' توابعی باشند که روی زیرمجموعه‌ای از اعداد حقیقی تعریف شده باشند آنگاه داریم:

 

به عنوان مثال فرض کنید

{{چپ چین}}

{{پایان چپ چین}}

تابع با نرخ رشد سریع تر همان تابع از مرتبه بیشتر است یعنی: 6''x''⁴. حال قانون دوم را اجرا می‌کنبم:

 

6''x''⁴ ضرب 6 و ''x''⁴ است که اولی به x وابسطه نیست بنابراین آن را حذف می‌کنیم و تنها ''x''⁴ می‌ماند در نتیجه : ''(f'' (''x'') = O (''x''⁴

 

علامت O بزرگ دو دامنه کاربرد دارد:

 

 

در هر دو کاربرد تابع (''g'' (''x''که در ''O''(...) به گونه‌ای انتخاب می‌شود که تا حد امکان ساده باشد.

علامت O بزرگ اولین بار توسط متخصص اعداد [[Paul Bachmann]] در سال 1894 , در جلد دوم کتاب ''Analytische Zahlentheorie'' معرفی شد (که جلد اولش در سال 1892 چاپ شده و شامل این علامت نبود). این علامت در کارهای [[نظریه اعداد]] توسط [[Edmund Landau]] متداول شد و به همین خاطر گاهی از آن به نام Landau symbol یاد می‌شود.

 

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

{{چپ چین}}

*[[Donald Knuth]]. ''[http://doi.acm.org/10.1145/1008328.1008329 Big Omicron and big Omega and big Theta]'', ACM SIGACT News, Volume 8, Issue 2, 1976.

*http://en.wikipedia.org/wiki/Big_O_notation

 

{{پایان چپ چین}}

{{مرتب‌سازی}}

[[رده:محاسبات عددی]]