نماد O بزرگ
From Wikipedia, the free encyclopedia
نماد O بزرگ (به انگلیسی: Big O notation) یک نماد ریاضیاتی ست که برای توصیف رفتار حدی یک تابع (وقتی آرگومانهای آن به بینهایت میل کند) به کار میرود.
این نماد (مخفف Order of growth (به فارسی: مرتبهٔ رشد)) اولین بار برای تحلیل سرعت الگوریتمهای رایانشی ابداع شد و بعدها به حسابان و نظریّهٔ اعداد گسترش یافت.
در علوم رایانه و نظریهٔ پیچیدگی محاسباتی، این نماد برای تحلیل الگوریتمها و دستهبندی و مقایسهٔ الگوریتمهای متفاوتِ موجود برای حل یک مسئلهٔ خاص به کار میرود. پیچیدگی محاسباتی نشاندهندهٔ رابطهٔ میان «دادهها» با «مقدار زمان یا مقدار حافظهٔ مورد نیاز برای پیدا کردن جواب» است و برای توصیف آن از این نماد استفاده میشود.[1]
در نظریهٔ تحلیلی اعداد، این نماد برای توصیف میزان دقت یک تقریب به کار میرود. یکی از مثالهای معروف این موضوع در قضیهٔ اعداد اول است: اگر تعداد اعداد اول کمتر از باشد، آنگاه .
در حسابان نیز این نماد در تحلیل مجانبی و سریهای تیلور کاربرد دارد.
به دلیل توصیف رفتار حدی، نماد به ریاضیدانها اجازه میدهد که تابع را ساده کنند تا بر روی نرخ رشد آن متمرکز شود؛ بنابراین توابع مختلف با نرخ رشد یکسان میتوانند دارای یک نماد مشابه باشند و در نتیجه در یک دسته قرار بگیرند.
نماد معروفترین عضو از مجموعهای از نمادهای دیگری همچون (کوچک) و ... است که ابداعات پاول باخمن (به آلمانی: Paul Bachmann)[2] و ادموند لانداو (به آلمانی: Edmund Landau)[3] بوده اند؛ به همین دلیل به اینها نمادهای باخمن-لانداو و یا نمادهای مجانبی (به انگلیسی: asymptotic notations) گفته میشود.