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

نمادهای مجانبی الگوریتم
برای تخمین زمان اجرای الگوریتم و میزان پیچیدگی آن، از نمادهایی به نام نمادهای مجانبی (حدی) استفاده میشود. این نمادها عباتند از: 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))
سپاسگذارم
مرسی خیلی خوب بود
خیلی مختصر و مفید بود
سلام, ممنون از زحماتتون اما خواندن متن بدلیل جابجایی نماد های ریاضی بسیار سخت است.
سلام مطالب بسیار خوبی بود