نماد O بزرگ

نماد O بزرگ. نماد O بزرگ ( به انگلیسی: Big O notation ) یک نماد ریاضیاتی ست که برای توصیف رفتار حدی یک تابع ( وقتی آرگومان های آن به بی نهایت میل کند ) به کار می رود.
این نماد ( مخفف Order of growth ( به فارسی: مرتبهٔ رشد ) ) اولین بار برای تحلیل سرعت الگوریتم های رایانشی ابداع شد و بعدها به حسابان و نظریّهٔ اعداد گسترش یافت.
در علوم رایانه و نظریهٔ پیچیدگی محاسباتی، این نماد برای تحلیل الگوریتم ها و دسته بندی و مقایسهٔ الگوریتم های متفاوتِ موجود برای حل یک مسئلهٔ خاص به کار می رود. پیچیدگی محاسباتی نشان دهندهٔ رابطهٔ میان «داده ها» با «مقدار زمان یا مقدار حافظهٔ مورد نیاز برای پیدا کردن جواب» است و برای توصیف آن از این نماد استفاده می شود. [ ۱]
در نظریهٔ تحلیلی اعداد، این نماد برای توصیف میزان دقت یک تقریب به کار می رود. یکی از مثال های معروف این موضوع در قضیهٔ اعداد اول است: اگر π ( x ) تعداد اعداد اول کمتر از x باشد، آنگاه π ( x ) ∼ x ln ⁡ ( x ) .
در حسابان نیز این نماد در تحلیل مجانبی و سری های تیلور کاربرد دارد.
به دلیل توصیف رفتار حدی، نماد O به ریاضی دان ها اجازه می دهد که تابع را ساده کنند تا بر روی نرخ رشد آن متمرکز شود؛ بنابراین توابع مختلف با نرخ رشد یکسان می توانند دارای یک نماد O مشابه باشند و در نتیجه در یک دسته قرار بگیرند.
نماد O معروفترین عضو از مجموعه ای از نمادهای دیگری همچون o ( کوچک ) و . . . است که ابداعات پاول باخمن ( به آلمانی: Paul Bachmann ) [ ۲] و ادموند لانداو ( به آلمانی: Edmund Landau‎ ) [ ۳] بوده اند؛ به همین دلیل به این ها نمادهای باخمن - لانداو و یا نمادهای مجانبی ( به انگلیسی: asymptotic notations ) گفته می شود.
فرض کنید که f ( n ) تابعی باشد که بخواهیم آن را توصیف کنیم و g ( n ) نیز یک تابع فرضی ست و همچنین f و g توابع مثبت هستند.
هر نماد دو تعریف معمول و تعریف حدی دارد ( که طبق قضیه هایی معادل یکدیگر هستند و به یک مفهوم اشاره دارند ) .
نمادهای O و Θ پرکاربردترین اینها هستند.
f ∈ O ( g ) ⟺ ∃ c , n 0 : ∀ n ⩾ n 0 : 0 ⩽ f ( n ) ⩽ c g ( n ) [ ۱]
به این معنی که از یک مقدار n خاصی ( n 0 ) بیشتر، تابع f از ضریبی از تابع g کمتر یا مساوی است.