نماد O بزرگ: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات: تصحیح جایگذاری کاما، شمارگان هزارگان |
جز ربات: تصحیح کاما، شمارگان هزارگان |
||
خط ۱:
در [[پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]]، '''نماد O بزرگ''' {{انگلیسی|Big O notation}} برای نشان دادن رابطه میان تعداد داده‌ها و منابع محاسباتی مورد نیاز برای حل یک مسأله با استفاده از یک [[الگوریتم]] استفاده می‌شود. استفاده از این نماد معمولاً برای بررسی زمان و یا حافظه مورد نیاز برای حل مسأله‌ای با تعداد زیادی ورودی می‌باشد.
در ریاضیات علامت O بزرگ رفتار حدی یک تابع را وقتی آرگومان‌های آن به یک عدد خاص یا به بینهایت میل
هرچند این علامت به عنوان بخشی از ریاضیات محض گسترش یافت ولی هم اکنون در [[پیچیدگی محاسباتی|تئوری‌های پیچیدگی محاسبات]] هم مکرراً استفاده می‌شود.
خط ۴۵:
در استفاده معمولی تعریف دقیق و رسمی علامت 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>. حال قانون دوم را اجرا می‌کنبم:
خط ۶۱:
علامت O بزرگ دو دامنه کاربرد دارد:
* در ریاضیات معمولاً برای نشان دادن این که یک [[سری هندسی]] متناهی تا چه اندازه به تابع مورد نظر نزدیک
* در علوم کامپیوتر این علامت در تحلیل الگوریتم‌ها کاربرد دارد.
خط ۶۷:
در هر دو کاربرد تابع (''g'' (''x''که در ''O''(...) به گونه‌ای انتخاب می‌شود که تا حد امکان ساده باشد.
== تاریخچه ==
علامت O بزرگ اولین بار توسط متخصص اعداد [[Paul Bachmann]] در سال
این علامت در [[علوم کامپیوتر]] توسط [[Donald Knuth]] (که علامت‌های مربوطه [[امگا]] و [[تتا]] را نیز برای اولین بار معرفی کرد) مشهور شد.او هم چنین متذکر شد که [[علامت امگا]] توسط Hardy و Littlewood تحت معنی اندکی متفاوت قبلاً تعریف شده بوده‌است.
| |||