شما اینجایید
خانه > آموزش > نمادهای مجانبی در طراحی الگوریتم و مرتبه زمانی

نمادهای مجانبی در طراحی الگوریتم و مرتبه زمانی

نمادهای مجانبی در الگوریتم ها – Asymptotic Notation

Asymptotic Notation نمادهای مجانبی در الگوریتم ها
Asymptotic Notation – نمادهای مجانبی در الگوریتم ها

برای تخمین زمان اجرای الگوریتم و میزان پیچیدگی آن، از نمادهایی به نام نمادهای مجانبی (حدی) استفاده میشود. این نمادها عباتند از: O ، Ω، Θ و o، ω که هر کدام طبق روش خاصی محاسبه میشوند و در تحلیل الگوریتم کاربرد فراوانی دارند.

رشد توابع

گوییم رشد تابع f(n) از تابع g(n) بیشتر است اگر n به بینهایت میل کند (n \to \infty) آنگاه f(n) زودتر به ∞ میل میکند. ترتیب رشد زیر برای توابع نام برده قابل اثبات است:

    \[ \small 1 < logn < n < nlogn < n^{2} < n^{3} < n^{4} < ... < 2^{n} < 3^{n} < 4^{n} < ... < n! < n^{n} \]

۱ یعنی بدون رشد، یعنی به n وابسته نیست. مثلا حلقه ای که ۱۰۰۰ بار اجرا میشود رشدش ۱ است.

برای مقایسه رشد توابع میتوان از حد زیر استفاده کرد:

    \[ \lim_{n\to\infty }\frac{f(n)}{g(n)} \]

  • اگر جواب حد برابر صفر باشد، نتیجه میگیریم، رشد f از g کمتر است.
  • اگر جواب برابر ∞ باشد، رشد f از g بیشتر است.
  • اگر برابر k ۰  باشد، f و g رشد یکسان دارند.

وقتی اندازه ورودی (n) بزرگ باشد، بیان دقیق زمان اجرا برحسب n ضروری نیست زیرا جمله با بزرگترین درجه در زمان موثر است. مثلا اگر زمان اجرای الگوریتمی 2n^3 + n^2 + n باشدف به ازای nهای بزرگ فقط n^3 مهم است. میتوان با نمادهای مجانبی این تفسیر را بهتر نشان داد. در بیان نمادها فرض میشود که دامنه اعداد طبیعی N={0, 1, 2, …} است.

نماد O بزرگ

در نظریهٔ پیچیدگی محاسباتی، نماد O بزرگ (به انگلیسی: Big O notation) برای نشان دادن رابطه میان تعداد داده‌ها و منابع محاسباتی مورد نیاز برای حل یک مسأله با استفاده از یک الگوریتم استفاده می‌شود. استفاده از این نماد معمولاً برای بررسی زمان و یا حافظه مورد نیاز برای حل مسأله‌ای با تعداد زیادی ورودی می‌باشد.

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

هرچند این علامت به عنوان بخشی از ریاضیات محض گسترش یافت ولی هم اکنون در تئوری‌های پیچیدگی محاسبات هم بارها استفاده می‌شود. بدترین حالت یا حالت میانگین زمان اجرا یا حافظه مورد استفاده یک الگوریتم اغلب به صورت تابعی از طول داده ورودی با استفاده از علامت O بزرگ توصیف می‌شود.

این به طراحان الگوریتم اجازه می‌دهد که رفتار الگوریتم‌هایشان را پیش‌بینی کنند و تصمیم بگیرند که کدام الگوریتم را استفاده کنند (بدون توجه به معماری رایانه یا میزان آهنگ ساعت آن).

برخلاف نماد Θ که یک تابع را از بالا و پایین بصورت مجانبی (حدی) محدود می کند، نماد O یک کران بالای حدی مشخص میکند. وقتی تابعی را با استفاده از علامت O بزرگ توصیف می‌کنیم بطور معمول تنها یک کران بالا برای نرخ رشد آن تابع فراهم می‌کنیم.

    \[ O(g(n))={\{f(n): \exists \ C, n_{0} > 0 \ that \ \forall \ n \geq n_{0}\ we\ have\ 0\leq f(n)\leq Cg(n)\}} \]

نمودار نماد O بزرگ
نمودار نماد O بزرگ

O(g(n)) ={ f(n) : وجود دارد C , n₀ >0 ,   به ازای  n >= n₀ : ۰ <= f(n) <= Cg(n) }

بنابراین O یک کران بالا برای تابع مشخص میکند. ما مینویسیم f(n) = O(g(n)) اگر f(n) عضوی از O(g(n)) باشد.

نکته : وقتی گفته می­شود زمان اجرای الگوریتم O(n^2) است یعنی الگوریتم هر جوری اجرا شود، مرتبه­ ی زمانی اجرای آن یا n2 است و یا از n2 کمتر است.

فواید

علامت O بزرگ دو دامنه کاربرد دارد:

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

در هر دو کاربرد تابع g(x) که در O(...) به گونه‌ای انتخاب می‌شود که تا حد امکان ساده باشد.

نماد امگا Ω

نماد Ω یک کران پایین حدی برای تابع مشخص میکند:

    \[ \Omega(g(n))={\{f(n): \exists \ C, n_{0}>0 \ that \ \forall \ n \geq n_{0}\ we\ have\ 0\leq Cg(n)\leq f(n) \}} \]

نمودار نماد امگا Ω
نمودار نماد امگا Ω

Ω(g(n)) ={ f(n) : وجود دارد C , n₀ >0 ,  به ازای   n >= n₀ : ۰ <=  Cg(n) <=  f(n)  }

نکته : وقتی گفته می­شود زمان اجرای الگوریتم \Omega(n^2) است یعنی الگوریتم هر جوری اجرا شود مرتبه­ ی زمانی اجرای آن n2 یا بیشتر از n2 است.

نماد تتا Θ

برای تابع g(n), \Theta(g(n)) یک مجموعه توابع است که به شکل زیر تعریف میشود:

    \[ \Theta(g(n))={\{f(n): \exists \ C1, C2, n_{0}>0 \ that \ \forall \ n \geq n_{0}\ we\ have\ 0\leq C1g(n)\leq f(n)\leq C2g(n)\}} \]

خوانده می شود:

تتا(جی(ان)) برابر است با اف(ان) به طوری که وجود دارد سی۱، سی۲ و ان۰ی بزرگتر از ۰ که به ازای هر ان بزرگتر مساوی ‘ان۰’ داریم: ۰ کوچکتر مساوی سی۱ جی(ان) کوچکتر مساوی اف(ان) کوچکتر مساوی سی۲ جی(ان)

نمودار نماد تتا Θ
نمودار نماد تتا Θ

Θ(g(n)) ={ f(n) : وجود دارد C1 , C2 , n₀ >0 , که به ازای هر  n >= n₀ : ۰ <=  C1g(n) <= f(n) <= C2g(n) }

یعنی تابع f(n) عضو \Theta(g(n)) است یا مینویسیم f(n) = \Theta(g(n)) هرگاه اعداد ثابت C1 و C2 وجود داشته باشند که برای nهای به اندازه کافی بزرگ f(n) بین C_{1}g(n) و C_{2}g(n) ساندویچ شود. بنابراین یک چند جمله ای درجه m که m ثابت است، از مرتبه \Theta(n^m) است و بطور کلی Θ دقیقا مرتبه رشد تابع را تعیین میکند.

نکته : وقتی گفته می­شود زمان اجرای الگوریتم \Theta(n^2) است یعنی الگوریتم هر جوری اجرا شود، مرتبه ­ی زمانی اجرای آن دقیقاً n2 خواهد بود.

زمان اجرای یک الگوریتم \Theta(g(n)) است اگر و فقط اگر بدترین حالت زمان O(g(n)) و بهترین حالت \Omega(g(n)) باشد.

نماد o (اُ کوچک)

نماد اُ کوچک، کران بالایی مشخص میکند که اکید است:

    \[ o(g(n))={\{f(n):\forall\ C>0, \exists\ n_{0} > 0 \ that \ \forall \ n \geq n_{0}\ we\ have\ 0\leq f(n)\leq Cg(n)\}} \]

o(g(n)) ={ f(n) : به ازای c>0 , وجود دارد n₀ >0 ,   به ازای  n >= n₀ : ۰ <= f(n) <= cg(n) }

یعنی نامساوی f(n)\leq Cg(n) باید به ازای همه اعداد مثبت c برقرار باشد، مثلاً  o(n^2) شامل همه توابعی است که رشدشان از n^2 کمتر است.

نماد امگا کوچک \omega

کران پایین اکید است.

    \[ \omega(g(n))={\{f(n):\forall\ C>0, \exists\ n_{0} > 0 \ that \ \forall \ n \geq n_{0}\ we\ have\ 0\leq Cg(n)\leq f(n)\}} \]

ω(g(n)) ={ f(n) : به ازای c>0 , وجود دارد n₀ >0 , به ازای  n >= n₀ : ۰ <= cg(n) <= f(n)}

پس ω(n^2) شامل همه توابعی است که رشدشان از n^2 بیشتر است.

مقایسه نمودارهای هر سه نماد O ، Ω، Θ
مقایسه نمودارهای هر سه نماد O ، Ω، Θ
  • بطور شهودی f(n) = O(g(n)) یعنی اینکه سرعت رشد f کمتر یا مساوی g است.
  • بطور شهودی f(n) = \Omega(g(n)) یعنی اینکه سرعت رشد f بیشتر یا مساوی g است.
  • بطور شهودی f(n) = \Theta(g(n)) یعنی اینکه سرعت رشد f مساوی g است.

مقایسه نمادها

نکته: به جهت شباهتی که مقایسه مجانبی دو تابع با مقایسه دو مقدار عددی حقیقی وجود داردمی توان این شباهت ها را به فرم زیر نشان داد:

    \[ f(n)=O(g(n)) \approx a\leq b \]

    \[ f(n)=\Omega(g(n)) \approx a\geq b \]

    \[ f(n)=\Theta(g(n)) \approx a=b \]

    \[ f(n)=o(g(n)) \approx a< b \]

    \[ f(n)=\omega(g(n)) \approx a>b \]

خاصیت تعدی (Transitivity)

    \[ f(n)=\Theta(g(n))\ and\ g(n)=\Theta (h(n))\rightarrow f(n)=\Theta (h(n)) \]

    \[ f(n)=O(g(n))\ and\ g(n)=O(h(n))\rightarrow f(n)=O(h(n)) \]

    \[ f(n)=\Omega(g(n))\ and\ g(n)=\Omega(h(n))\rightarrow f(n)=\Omega(h(n)) \]

    \[ f(n)=o(g(n))\ and\ g(n)=o(h(n))\rightarrow f(n)=o(h(n)) \]

    \[ f(n)=\omega (g(n))\ and\ g(n)=\omega(h(n))\rightarrow f(n)=\omega(h(n)) \]

خاصیت بازتابی (reflexivity)

Θ و O و Ω بازتابی یا انعکاسی هستند:

    \[ f(n) = O(f(n)) \]

    \[ f(n) = \Omega (f(n)) \]

    \[ f(n) = \Theta (f(n)) \]

خاصیت تقارنی (symmetry)

فقط Θ متقارن است:

    \[ f(n) = \Theta (g(n))\Leftrightarrow g(n)= \Theta (f(n)) \]

ترانهاده تقارنی

    \[ f(n) = O(g(n))\Leftrightarrow g(n)= \Omega (f(n)) \]

    \[ f(n) = o(g(n))\Leftrightarrow g(n)= \omega(f(n)) \]

موفق باشید.

نوتیف
امیدوارم مطالب نوتیف برایتان مفید واقع شده باشد. با عضویت در خبرنامه نوتیف مطالب تازه ما را در اینباکس خود داشته باشید. کانال ما در تلگرام هم راه سریع و مطمئنی برای آگاهی از مطالب ماست. *** من رضا حیدری مدیر وب سایت نوتیف هستم. همکنون مشغول به تحصیل در رشته کارشناسی ارشد نرم افزار بوده و به دنیای فناوری علاقه مندم به همین دلیل در نوتیف به دنبال نشر و ترویج موضوعات روز دنیای فناوری بخصوص موضوعات مرتبط با دنیای موبایل، اینترنت، کامپیوتر هستم. در کنار اینها گاهی هم گریزی به دیگر موضوعات مهم خواهیم زد که خالی از لطف نخواهد بود. با نوتیف همراه باشید بودن با شما افتخار بزرگی برای ماست.

2 thoughts on “نمادهای مجانبی در طراحی الگوریتم و مرتبه زمانی

  1. ممنونم ازوبسایت شما خیلی استفاده کردم مخصوص در مورد نمواد های جانبی در طراحی الگوریم فردا همین رو امتحان دارم.
    متشکرم

پاسخ دهید

هفده − 15 =

Top