نماد O بزرگ: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۱:
{{ادغام|علامت O بزرگ}}{{بدون منبع}}
در [[پیچیدگی محاسباتی|نظریهی پیچیدگی محاسباتی]]، '''نماد O بزرگ''' {{انگلیسی|Big O notation}} برای نشان دادن رابطه میان تعداد دادهها و منابع محاسباتی مورد نیاز برای حل یک مسأله با استفاده از یک [[الگوریتم]] استفاده میشود. استفاده از این نماد معمولاً برای بررسی زمان و یا حافظه مورد نیاز برای حل مسألهای با تعداد زیادی ورودی میباشد.
در ریاضیات علامت O بزرگ رفتار حدی یک تابع را وقتی آرگومان های آن به یک عدد خاص یا به بینهایت میل می کند, توصیف می کند.علامت O بزرگ به کاربر اجازه می دهد که تابع را ساده کند تا بر روی نرخ رشد آن متمرکز شود. بنابراین توابع مختلف با نرخ رشد یکسان می توانند دارای یک علامت O مشابه باشند.
هرچند این علامت به عنوان بخشی از ریاضیات محض گسترش یافت ولی هم اکنون در تئوری های پیچیدگی محاسبات هم مکرراً استفاده می شود.
بدترین حالت یا حالت میانگین زمان اجرا یا حافظه مورد استفاده یک الگوریتم غالباً به صورت تابعی از طول داده ورودی با استفاده از علامت O بزرگ توصیف می شود.
این به طراحان الگوریتم اجازه می دهد که رفتار الگوریتم هایشان را پیش بینی کنند و تصمیم بگیرند که کدام الگوریتم را استفاده کنند(بدون توجه به معماری کامپیوتر یا میزان آهنگ ساعت آن).
وقتی تابعی را با استفاده از علامت O بزرگ توصیف می کنیم معمولاً تنها یک کران بالا برای نرخ رشد آن تابع فراهم می کنیم. علامت های مرتبط دیگر برای توصیف توابع عبارتند از: o, Ω, ω, Θ.
==تعریف رسمی==
فرض کنید (''f'' (''x'') ,''g'' (''x'' توابعی باشند که روی زیرمجموعه ای از اعداد حقیقی تعریف شده باشند آنگاه داریم:
{{چپ چین}}
:<math>f(x)=O(g(x))\mbox{ as }x\to\infty\,</math>
{{پایان چپ چین}}
اگر و تنها اگر عدد حقیقی مثبت ''M'' و عدد حقیقی ''x'' <sub>0</sub> موجود باشد به طوری که:
{{چپ چین}}
<math>|f(x)| \le \; M |g(x)|\mbox{ for all }x>x_0.</math>
{{پایان چپ چین}}
این علامت برای توصیف رفتار تابع نزدیک یک عدد حقیقی مانند ''a'' (معمولاً, ''a'' = 0)
نیز به کار می رود:
{{چپ چین}}
<math>f(x)=O(g(x))\mbox{ as }x\to a\,</math>
{{پایان چپ چین}}
اگر و تنها اگر عدد مثبتی مانند ''δ'' و ''M'' موجود باشند به طوری که:
{{چپ چین}}
<math>|f(x)| \le \; M |g(x)|\mbox{ for }|x - a| < \delta.</math>
{{پایان چپ چین}}
== مثال ==
سطر ۱۰ ⟵ ۴۳:
<center><math>T(n)= O(n^2)</math></center>
این بدان معنی است که اگر تعداد ورودی ۲ برابر شود زمان حل (با فرض زیاد بودن تعداد ورودی) ۴ برابر خواهد شد.
در استفاده معمولی تعریف دقیق و رسمی علامت O مورد استفاده قرار نمی گیرد بلکه علامت O بزرگ برای تابع (''f'' (''x'' به صورت زیر ساده می شود:
*اگر (''f'' (''x''مجموع توابع مختلف باشد , تابع با سرعت رشد بیشتر را نگه داشته و بقیه را حذف می کنیم.
*اگر (''f'' (''x''مضربی از چند فاکتور مختلف باشد هر مقدار ثابتی را حذف می کنیم.
به عنوان مثال فرض کنید
{{چپ چین}}
''f'' (''x'') = 6''x''<sup>4</sup> − 2''x''<sup>3</sup> + 5
{{پایان چپ چین}}
و ما می خواهیم این تابع را با استفاده از علامت O بزرگ ساده کنیم, این تابع مجموع سه تابع 6''x''<sup>4</sup>, −2''x''<sup>3</sup>, و 5 است.
تابع با نرخ رشد سریع تر همان تابع از مرتبه بیشتر است یعنی : 6''x''<sup>4</sup>.
حال قانون دوم را اجرا می کنبم:
6''x''<sup>4</sup> ضرب 6 و ''x''<sup>4</sup> است که اولی به x وابسطه نیست بنابراین آن را حذف می کنیم و تنها ''x''<sup>4</sup>
می ماند در نتیجه : ''(f'' (''x'') = O (''x''<sup>4</sup>
==فواید==
علامت O بزرگ دو دامنه کاربرد دارد:
*در ریاضیات معمولاً برای نشان دادن این که یک سری هندسی متناهی تا چه اندازه به تابع مورد نظر نزدیک است ,خصوصاً در مورد سری تیلور ناقص از این علامت استفاده می شود.
*در علوم کامپیوتر این علامت در تحلیل الگوریتم ها کاربرد دارد.
در هر دو کاربرد تابع (''g'' (''x''که در ''O''(...) به گونه ای انتخاب می شود که تا حد امکان ساده باشد.
==تاریخچه==
علامت O بزرگ اولین بار توسط متخصص اعداد [[Paul Bachmann]] در سال 1894 , در جلد دوم کتاب ''Analytische Zahlentheorie'' معرفی شد (که جلد اولش در سال 1892 چاپ شده و شامل این علامت نبود). این علامت در کارهای [[نظریه اعداد]] توسط [[Edmund Landau]] متداول شد و به همین خاطر گاهی از آن به نام Landau symbol یاد می شود.
این علامت در [[علوم کامپیوتر]] توسط [[Donald Knuth]] (که علامت های مربوطه [[امگا]] و [[تتا]] را نیز برای اولین بار معرفی کرد) مشهور شد.او هم چنین متذکر شد که [[علامت امگا]] توسط Hardy و Littlewood تحت معنی اندکی متفاوت قبلاً تعریف شده بوده است.
[[en:Big O notation]]
==منابع==
{{چپ چین}}
*[[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.
*[[Nicholas J. Higham]],''Handbook of writing for the mathematical sciences'', SIAM. ISBN 0898714206, p. 25
*http://en.wikipedia.org/wiki/Big_O_notation
{{پایان چپ چین}}
[[رده:محاسبات عددی]]
|