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

مدیران انجمن: parse, javad123javad

ارسال پست
نمایه کاربر
rohamavation

نام: roham hesami radرهام حسامی راد

محل اقامت: 100 مایلی شمال لندن جاده آیلستون، لستر، لسترشر. LE2

عضویت : سه‌شنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴


پست: 3222

سپاس: 5492

جنسیت:

تماس:

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

پست توسط rohamavation »

برای تخمین زمان اجرای الگوریتم و میزان پیچیدگی آن، از نمادهایی به نام نمادهای مجانبی (حدی) استفاده میشه. این نمادها 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 بزرگ نمودار نماد 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^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₀ : 0 <= 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)}}$
تتا(جی(ان)) برابر است با اف(ان) به طوری که وجود دارد سی1، سی2 و ان0ی بزرگتر از 0 که به ازای هر ان بزرگتر مساوی ‘ان0’ داریم: 0 کوچکتر مساوی $C1g(n) $ کوچکتر مساوی$f_n$ کوچکتر مساوی$C2g(n) $
تتا Θ نمودار نماد تتا Θ
$Θ(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)$ است یعنی الگوریتم هر جوری اجرا شود، مرتبه ­ی زمانی اجرای آن دقیقاً n2 خواهد بود.
زمان اجرای یک الگوریتم $\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 بیشتر است.
مقایسه نمودارهای هر سه نماد O ، Ω، Θ
مقایسه نمودارهای هر سه نماد 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))$
موفق باشید.
Tags: Asymptotic Notations نماد O نماد Θ نماد Ω نماد امگا نماد
چکیده متن منمجانبی (یا تابع مجانبی) به سادگی تابع (یا رابطه) g(n) دیگری است که با بزرگتر و بزرگتر شدن n، f(n) به طور فزاینده ای به آن نزدیک می شود، اما هرگز کاملاً به آن نمی رسد. مزیت صحبت در مورد توابع مجانبی این است که به طور کلی صحبت در مورد آنها بسیار ساده تر است حتی اگر عبارت f(n) بسیار پیچیده باشد. توابع مجانبی به عنوان بخشی از نمادهای مرزی استفاده می شوند که f(n) را در بالا یا پایین محدود می کنند.
(توجه: به معنای به کار رفته در اینجا، توابع مجانبی تنها پس از تصحیح برخی ضریب ثابت غیر صفر به تابع اصلی نزدیک هستند، زیرا هر سه نماد بزرگ-O/Θ/Ω از در نظر گرفتن این عوامل ثابت صرف نظر می‌کنند.)
سه نماد کران مجانبی چیست و چگونه متفاوت هستند؟
هر سه نماد به این صورت استفاده می شود:
$f(n) = O(g(n))$
که در اینجا f(n) تابع مورد نظر است و g(n) تابع مجانبی دیگری است که می‌خواهید f(n) را با آن تقریب بزنید. این نباید به عنوان یک برابری به معنای دقیق در نظر گرفته شود، بلکه یک بیانیه رسمی بین سرعت رشد f(n) نسبت به n در مقایسه با g(n) است، زیرا n بزرگ می شود. ناب شناسان اغلب از نماد جایگزین $f(n) ∈ O(g(n))$ استفاده می کنند تا تاکید کنند که نماد O(g(n)) در واقع یک خانواده کامل از توابع است که نرخ رشد مشترکی دارند.
نماد Big-ϴ (تتا) برابری را در رشد f(n) تا یک عامل ثابت بیان می‌کند. برای نرخ رشد شبیه عملگر = عمل می کند.
نماد Big-O یک کران بالای رشد f(n) را توصیف می کند. برای نرخ رشد شبیه عملگر ≤ عمل می کند.
نماد Big-Ω (امگا) یک کران پایین را در رشد f(n) توصیف می کند. برای نرخ رشد شبیه عملگر ≥ عمل می کند.
بسیاری از نمادهای مجانبی دیگر وجود دارد،
نمادهای Big-O و امثال آن اغلب به عنوان راهی برای مقایسه پیچیدگی زمانی هستند.
نمودارهایی از توابع که معمولاً در تجزیه و تحلیل الگوریتم‌ها استفاده می‌شوند و تعداد عملیات N در مقابل اندازه ورودی n را برای هر تابع نشان می‌دهند.
نماد O بزرگ هنگام تجزیه و تحلیل الگوریتم ها برای کارایی مفید است. برای مثال، زمان (یا تعداد مراحل) که برای تکمیل یک مسئله با اندازه n طول می‌کشد، ممکن است T(n) = 4n2 − 2n + 2 باشد. با بزرگ‌تر شدن n، عبارت n2 غالب خواهد شد. به طوری که می توان از تمام اصطلاحات دیگر صرف نظر کرد - برای مثال وقتی n = 500، عبارت 4n2 1000 برابر بزرگتر از جمله 2n است. نادیده گرفتن مورد دوم تأثیر ناچیزی بر ارزش عبارت برای بیشتر اهداف خواهد داشت. علاوه بر این، ضرایب بی ربط می شوند اگر با هر ترتیب بیان دیگری مقایسه کنیم، مانند عبارتی که شامل یک عبارت n3 یا n4 است. حتی اگر T(n) = 1,000,000n2، اگر U(n) = n3، دومی همیشه زمانی که n بزرگتر از 1,000,000 شود از حالت اول فراتر می رود (T(1,000,000) = 1,000,0003 = U(1,000,000)). علاوه بر این، تعداد مراحل بستگی به جزئیات مدل ماشینی دارد که الگوریتم روی آن اجرا می‌شود، اما انواع مختلف ماشین‌ها معمولاً تنها با یک عامل ثابت در تعداد مراحل مورد نیاز برای اجرای یک الگوریتم تغییر می‌کنند. بنابراین نماد O بزرگ آنچه را که باقی می‌ماند نشان می‌دهد: هر دو را می‌نویسیم${\displaystyle T(n)=O(n^{2})}$
یا${\displaystyle T(n)\in O(n^{2})}$
و بگویید که الگوریتم دارای مرتبه پیچیدگی زمانی n2 است. علامت "=" به معنای "برابر است" به معنای ریاضی عادی آن نیست، بلکه بیشتر به معنای "است" است، بنابراین عبارت دوم گاهی دقیق تر در نظر گرفته می شود (به بحث "علامت برابری" در زیر مراجعه کنید) اولی را برخی سوء استفاده از علامت گذاری می دانندمجانبی بی نهایت کوچک
Big O همچنین می تواند برای توصیف عبارت خطا در تقریبی به یک تابع ریاضی استفاده شود. مهم‌ترین عبارات به‌صراحت نوشته می‌شوند، و سپس کم‌اهمیت‌ترین عبارت‌ها در یک عبارت O بزرگ خلاصه می‌شوند. برای مثال سری نمایی و دو عبارت آن را در نظر بگیرید که وقتی x کوچک است معتبر هستند:${\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\[4pt]&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\[4pt]&=1+x+O(x^{2})&{\text{as }}x\to 0\end{aligned}}}$
عبارت دوم (کسی که O(x3) دارد) به این معنی است که مقدار مطلق خطای ex − (1 + x + x2/2) حداکثر چند بار ثابت است |x3| وقتی x به اندازه کافی به 0 نزدیک است.
f تابع f را می‌توان به صورت مجموع محدودی از توابع دیگر نوشت، سپس تابعی که سریع‌ترین رشد را دارد ترتیب f(n) را تعیین می‌کند. مثلا،
${\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .}$
به طور خاص، اگر تابعی ممکن است توسط یک چند جمله ای در n محدود شود، از آنجایی که n به بی نهایت تمایل دارد، ممکن است شرایط مرتبه پایین چند جمله ای را نادیده بگیریم. مجموعه های O(nc) و O(cn) بسیار متفاوت هستند. اگر c بزرگتر از یک باشد، دومی خیلی سریعتر رشد می کند. تابعی که برای هر c سریعتر از nc رشد می کند ابرچند جمله ای نامیده می شود. تابعی که کندتر از هر تابع نمایی به شکل cn رشد می کند، تحت نمایی نامیده می شود. یک الگوریتم می تواند به زمانی نیاز داشته باشد که هم ابرچندجمله ای و هم تحت نمایی باشد. نمونه هایی از این شامل سریع ترین الگوریتم های شناخته شده برای فاکتورسازی اعداد صحیح و تابع nlog n است.
ممکن است هر توان n را در داخل لگاریتم نادیده بگیریم. مجموعه O(log n) دقیقا مشابه O(log(nc)) است. لگاریتم ها فقط با یک عامل ثابت تفاوت دارند (زیرا log(nc) = c log n) و بنابراین نماد O بزرگ آن را نادیده می گیرد. به طور مشابه، سیاهههای مربوط با پایه های ثابت مختلف معادل هستند. از سوی دیگر، نمایی با پایه های مختلف از یک ترتیب نیست. به عنوان مثال، 2n و 3n ترتیب یکسانی ندارند.
تغییر واحدها ممکن است بر ترتیب الگوریتم حاصل تأثیر بگذارد یا نه. تغییر واحدها معادل ضرب متغیر مناسب در یک ثابت در هر کجا که ظاهر می شود است. به عنوان مثال، اگر الگوریتمی به ترتیب n2 اجرا شود، جایگزینی n با cn به این معنی است که الگوریتم به ترتیب c2n2 اجرا می شود و نماد O بزرگ ثابت c2 را نادیده می گیرد. این را می توان به صورت c2n2 = O(n2) نوشت. با این حال، اگر یک الگوریتم به ترتیب 2n اجرا شود، با جایگزینی n با cn، 2cn = (2c)n به دست می آید. این به طور کلی معادل 2n نیست. تغییر متغیرها نیز ممکن است بر ترتیب الگوریتم حاصل تأثیر بگذارد. به عنوان مثال، اگر زمان اجرای یک الگوریتم زمانی که بر حسب تعداد n ارقام یک عدد ورودی x اندازه‌گیری می‌شود O(n) باشد، زمانی که به عنوان تابعی از خود عدد ورودی x اندازه‌گیری شود، زمان اجرای آن$ O(log x)$ است. ، زیرا $n = O (log x).$
تصویر

ارسال پست