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

 

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

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

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

 

رشد توابع

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

1 < lgn < n< nlgn < n² < n³ < n⁴ < … < ⁿ2 < 3ⁿ < 4ⁿ < …< n! < nⁿ

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

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

lim n -> ∞ f(n)/g(n)

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

 

نمادهای مجانبی Asymptotic notation

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

 

نماد Θ

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

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

یعنی تابع f(n) عضو Θ(g(n)) است یا مینویسیم f(n) = Θ(g(n)) هرگاه اعداد ثابت C1 و C2 وجود داشته باشند که برای nهای به اندازه کافی بزرگ f(n) بین C1g(n) و C2g(n) ساندویچ شود.

بنابراین یک چند جمله ای درجه m که m ثابت است، از مرتبه(nͫ) Θ است و بطور کلی Θ دقیقا مرتبه رشد تابع را تعیین میکند.

 

نماد O 

نماد Θ یک تابع را از بالا و پایین بصورت مجانبی (حدی) محدود میکرد.

نماد O یک کران بالای حدی مشخص میکند:

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²) شامل همه توابعی است که رشدشان کمتر یا مساوی n² است.

 

نماد Ω

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

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

بطور کلی Ω(n²) شامل همه توابعی است که رشدشان بیشتر یا مساوی n² است.

 

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

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

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

یعنی نامساوی f(n) <=  Cg(n) باید به ازای همه اعداد مثبت c برقرار باشد، مثلا o(n²) شامل همه توابعی است که رشدشان از n² کمتر است.

 

نماد ω

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

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

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

 

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

تعدی (transtivity)

f(n) = Θ (g(n)) and g(n) = Θ (h(n))  imply  f(n) = Θ (h(n)) 

بجای Θ میتوان سایر نمادها را نیز قرار داد.

 

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

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

f(n) = Θ (f(n))

f(n) = O (f(n))

f(n) = Ω (f(n))

تقارنی (symmetry)

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

f(n) = Θ (g(n)) if  and  only  g(n)= Θ (f(n))

 

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

f(n) = O (g(n)) if  and  only  g(n)= Ω (f(n))

f(n) = o (g(n)) if  and  only  g(n)= ω (f(n))