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

نمادهای مجانبی در طراحی الگوریتم – 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}

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

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

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

• اگر جواب حد برابر صفر باشد، نتیجه میگیریم، رشد f از g کمتر است.
• اگر جواب برابر ∞ باشد، رشد f از g بیشتر است.
• اگر برابر k ≠ 0  باشد، 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(g(n)) ={ f(n) : وجود دارد C , n₀ >0 ,   به ازای  n >= n₀ : 0 <= f(n) <= Cg(n) }

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

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

فواید

علامت 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₀ : 0 <=  Cg(n) <=  f(n)  }

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

نماد تتا Θ

برای تابع 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)}}

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

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

Θ(g(n)) ={ f(n) : وجود دارد C1 , C2 , n₀ >0 , که به ازای هر  n >= n₀ : 0 <=  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) است یعنی الگوریتم هر جوری اجرا شود، مرتبه ­ی زمانی اجرای آن دقیقاً n² خواهد بود.

زمان اجرای یک الگوریتم \Theta(g(n)) است اگر و فقط اگر بدترین حالت زمان و بهترین حالت O(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₀ : 0 <= f(n) <= cg(n) }

یعنی نامساوی f(n)\leq Cg(n)  باید به ازای همه اعداد مثبت 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₀ : 0 <= cg(n) <= f(n)}

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

• بطور شهودی 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))

موفق باشید.