• نماد O بزرگ
• موارد استفاده
• تقریب های چند جمله ای بی نهایت
• تعریف رسمی
• مواد نماد گذاری
• مرتبه های معمول توابع
• خواص
• متغیرهای چند گانه

نماد O بزرگ

نماد O بزرگ نمادی است که در نظریه پیچیدگی ، علوم کامپیوتر و ریاضیات برای توضیح رفتار تقریبی توابع بکار گرفته می شود. بصورت دقیقتر، از این نماد برای توضیح یک ’’’حد بالای تقریبی’’’ برای بزرگی یک تابع بصورت تابعی دیگر که معمولاً ساده تر است ، استفاده می گردد.

این نماد اولین بار توسط ادموند لاندو،نظریه پرداز اعداد آلمانی اختراع شد و به همین علت ’’’نماد لاندو’’’ نیز به آن می گویند. این O در اصل یک امیکرون بزرگ است؛ امروزه از حروف O بزرگ به جای آن استفاده می شود ولی هیچگاه رقم صفر بکار نمی رود.

در این دانش نامه، نمادهای متنوعی که در این مقاله توضیح داده شده اند ، برای تخمین زدن فرمولها ( مثلاً آنهائیکه در مقاله جمع بکار رفته اند) ، برای تجزیه و تحلیل الگوریتم ( مثلاً آنهائیکه در مقاله heapsort بکار رفته اند) و برای تعریف عبارات در نظریه پیچیدگی ( مثلاً زمان polynomial چند جمله ای مورد استفاده قرار گرفته اند.

موارد استفاده

دو مورد استفاده بسیار متفاوت ولی رسماً نزدیک بهم برای این نمادگذاری وجود دارد:تقریب های نامتناهی و تقریب های چند جمله ای نامتناهی. اما این تمایز تنها در کابرد است نه در اصول - تعریف رسمی ’’’O بزرگ’’’ در هر دو حالت یکسان است فقط در مبحث توابع حدود متفاوتی دارد.

تقریب های نامتناهی
نماد گذاری O بزرگ در هنگام تجزیه و تحلیل الگوریتم ها برای بررسی میزان کارایی مفید است. بعنوان مثال ، زمان ( یا تعداد مراحلی ) که طول می کشد تا برنامه ای به بزرگی n تکمیل گردد ممکن است T(n) = 4n2 - 2n + 2 باشد.

با بزرگ شدن n، عبارت n2 تعیین کننده خواهد شد. بنابراین می توان از بقیه عبارات صرف نظر کرد. بعلاوه ، ثوابت به جزئیات دقیق اجرا و سخت افزاری که برنامه را اجرا می کند بستگی خواهد داشت، بنابراین از آنها نیز می توان صرف نظر کرد. نماد O بزرگ چیزهای باقیمانده را در بر می گیرد: ما می نویسیم T(n) = O(n2) و می گوییم الگوریتم دارای پیچیدگی زمانی از مرتبة n2 می باشد.

تقریب های چند جمله ای بی نهایت

O بزرگ را همچنین می توان برای توضیح عبارت خطا در تقریب یک تابع ریاضی بکار برد. مثلاً


عبارت فوق بیان می کند که اگر x به حد کافی به صفر نزدیک باشد میزان خطا از نظر مقدار مطلق کوچکتر از مقداری ثابت ضربدر x3 است.

تعریف رسمی

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

f(x) is O(g(x» as x → ∞

اگر و تنها اگر اعداد M و x0 وجود داشته باشند بطوریکه :
|f(x)| ≤ M |g(x)| for x > x

همچنین می توان این نماد را برای توضیح رفتار f در نزدیکی عدد حقیقی a بکار برد .
می گوئیم:
f(x) is O(g(x» as x → a

اگر و تنها اگر اعداد δ>0 و M وجود داشته باشند ، بطوریکه :

|f(x)| ≤ M |g(x)| for |x - x0| < δ
اگر برای مقادیر x که به قدر کافی به a نزدیک هستند ، g(x) برابر صفر نباشد، هر دوی این تعاریف را می توان بوسیله برتری حدی بصورت واحدی در آورد.

f(x) is O(g(x» as x → a

اگر و تنها اگر



در ریاضیات هر دو رفتار تقریبی در نزدیکی و نزدیکی a در نظر گرفته شده اند. در نظریه پیچیدگی محاسباتی ، تنها از تقریب های نزدیک استفاده می گردد؛ بعلاوه ، تنها توابع مثبت در نظر گرفته می شوند، بنابراین احتمال دارد که مقادیر مثبت در نظر گرفته نشوند.

مواد نماد گذاری

f(x) is O(g(x) که بصورت فوق تعریف شده است اغلب بصورت f(x)=O(g(x» نوشته می شود. این روش نوشتن سوء استفاده ناچیزی از نمادگذاری است

ما حقیقتاً تساوی دو تابع را اعمال نمی کنیم.

برخی نویسندگان یک نماد گذاری مجموعه ای را ترجیح میدهند و می نویسند f ∈ O(g)، و به O(g) بصورت مجموعه ای از همه توابعی که g بر آنها تسلط دارد نگاه می کنند.

بعلاوه توابعی بصورت f(x)=h(x)+O(g(x» را باید به این صورت تعریف کرد:

تفاوت f(x) و h(x) برابر است با O(g(x» .

مرتبه های معمول توابع

در اینجا لیست توابعی را مشاهده می کنید که در هنگام تجزیه و تحلیل الگوریتم ها معمولاً با آنها مواجه می شویم. در مورد تمامی این توابع n→∞ است. توابعی که رشد کمتری دارند، در اول این لیست قرار گرفته اند. c هم یک ثابت اختیاری است.

نماد نام
O(1) ثابت
O(log n) لگاریتمی
O«log n)c) چند لگاریتمی
O(n) خطی
O(n log n) گاهی اوقات حسابی خطی خوانده می شود
O(n2) کواد راتیک
O(nc) چند جمله ای و گاهی هندسی
O(cn) نمایی
O(n!) فاکتوریل

خواص

اگر بتوان تابع f(n) را بصورت حاصل جمع متناهی از دیگر توابع نوشت، آنگاه تابعی که سریعتر از بقیه رشد می کند، مرتبة f(n) را تعیین خواهد کرد. بعنوان مثال:

f(n) = 10logn + 5(logn)3 + 7n + 3n2 + 6n3 = O(n3)

بطور کلی، اگر یک تابع توسط یک چند جمله ای به n محدود شود، آنگاه با میل کردن n به سوی بی نهایت ، می توان از عبارات مرتبة پایین تر چند جمله ای صرف نظر کرد.

O(nc) ; و O(cn) بسیار متفاوت هستند. O(cn) بسیار سریعتر رشد می کند بدون توجه به اینکه ثابت c چقدر بزرگ است. تابعی که سریعتر از هر توانی از n رشد می کند را ابر چند جمله ای می نامند. تابعی را که کندتر از هر تابع نمایی به شکل cn رشد می کند، زیرنمایی می نامند. یک الگوریتم ممکن است هم در زمانی معادل یک ابر چند جمله ای اجرا شود و هم در زمانی معادل یک زیر نمایی؛ مثالهایی از این دست شامل سریعترین الگوریتم هایی هستند که برای فاکتور گرفتن از اعداد صحیح می شناسیم.

O(logn) دقیقاً با O(log(nc» یکسان است. وجه تمایز و تفاوت الگوریتم ها تنها در یک ضریب ثابت است، ( از آنجائیکه log(nc)=clogn ) و بنابراین نماد O بزرگ این موضوع را نادیده می گیرد. به همین ترتیب لگاریتم هایی با ثوابت مختلف با هم معادل هستند.

اگر تابع f(x) توسط یک چند جمله ای به x محدود شود، آنگاه با میل کردن x به سوی صفر، ممکن است بتوان از عبارات مرتبه بالاتر هر چند جمله ای صرف نظر کرد. در مورد حالت تقریب های نامتناهی به این تفاوت دقت کنید.

نماد گذاریهای تقریبی مرتبط
O بزرگ متداولترین نماد گذاری تقریبی مورد استفاده برای مقایسه توابع است. ما برخی نمادهای دیگر را با اختصار بصورت عباراتی ازO بزرگ تعریف خواهیم کرد:

نماد تعریف
f(n) = O(g(n» حدبالایی تقریب
f(n) = o(g(n» از نظر تقریبی قابل صرف نظر کردن

f(n) =Ω(g(n» حد پایینی تقریب ())iffg«n» = O«f«n»»
f«n» = ω«g«n» از نظر تقریبی مسلط «iffg«n» = «f«n»»
f«n» = Θ«g«n» حد صلب تقریبی «iff f«n» = O«g«n» and g«n» = O«f«n»»

در اینجا می توان دریافت که چرا لاندو از این حروف یونانی استفاده کرده است:

امیکرون همان «اُ- میکرون » است به معنی o کوچک در حالیکه «اُمگا» به معنی «O بزرگ» است.


عبارت f«n»=o«g«n» بصورت «o f«n» ی کوچک g«n» است» خوانده می شود. این بدین معنی است که g«n» بسیار سریعتر از f«n» رشد می کند. بعبارت دیگر ، این عبارت بیان می کند که ««حد f(n)/g(n) صفر است.
از نمادهای Θ و Ωاغلب در علوم کامپیوتر استفاده می گردد، استفاده از o کوچک در ریاضیات متداول است ولی در علوم کامپیوتر به ندرت از آن استفاده می گردد. از ω کوچک به ندرت استفاده می گردد. اغلب در هنگام استفاده های سرسری ، در جائیکه منظور Θاست از o استفاده می شود، مثلا ممکن است بگویند: زمان اجرای ))heapsort عبارتست از O«nlogn» در حالت متوسط در حالیکه چیزی که مورد نظر بوده این جمله است: زمان اجرای heapsort(( عبارتست از«nlogn» Θ در حالت متوسط . هر دوی این عبارات صحیح است، ولی عبارت اخیر، ادعایی مستحکمتر می باشد.

نماد دیگری که گاهی در علوم کامپیوتر مورد استفاده قرار می گیرد Õ « بخوانید O – نرم»
f«n» = Õ«g«n» کوچک شده عبارت f«n» = O«g«n» logkn» برای تعدادی k است. این نماد ، همان O بزرگ است که در آن فاکتورهای لگاریتمی صرف نظر شده است. اغلب از این نماد برای توصیف گروهی از تخمین ها استفاده می گردد « زیرا برای هر مقدار ثابت k ، logkn همیشه o«n» است.»

متغیرهای چند گانه

O بزرگ «و o کوچک و Ω و...» را می توان با متغیرهای چند گانه نیز بکار برد.
بعنوان مثال عبارت :


چنین بیان می دارد که ثابت C و N وجود دارند، بطوریکه



به منظور جلوگیری از ابهام ، همیشه می بایست متغیرهایی را که اجرا می شوند مشخص نمود.عبارت :

کاملاً با عبارت مقابل متفاوت است: