نمادهای توابع رشد الگوریتم‌ها

الگوریتم ابزاری است که از آن برای حل‌مسئله استفاده می‌شود. گاهی‌اوقات بیش از یک الگوریتم برای حل یک مسئله وجود دارد؛ بنابراین بهینه بودن ابزارها حایز اهمیت است. مهم‌ترین پارامترهای بهینگی یک الگوریتم، میزان حافظه و زمانی است که برای اجرا مصرف می‌کند و این دو پارامتر، معیارهایی برای سنجش کارایی الگوریتم هستند. در این مقاله به تحلیل‌زمانی الگوریتم‌ها می‌پردازیم. یکی از روش‌های تحلیل‌زمانی الگوریتم بررسی زمان اجرا در بدترین‌حالت و حالت‌میانگین می‌باشد. توجه کنید که بهترین زمان اجرای الگوریتم اهمیت چندانی ندارد، چرا که این حالت معمولاً برای ورودی با تعداد کم و در شرایط خاص اتفاق می‌افتد و زمان اجرا هم اغلب آنقدر کوتاه است که مهم نیست از چه الگوریتمی استفاده می‌شود. بعضی مواقع پیچیدگی (منظور از پیچیدگی، تابعی است برحسب اندازه ورودی که زمان اجرای الگوریتم را بیان می‌کند. در ادامه بحث به چگونگی محاسبهٔ آن خواهیم‌پرداخت) حالت‌میانگین و بدترین‌حالت با یکدیگر تفاوت چندانی نمی‌کند اما معمولاً پیچیدگی الگوریتم در حالت‌میانگین بهتر از پیچیدگی آن در بدترین‌حالت است؛ چراکه اغلب بدترین‌حالت الگوریتم به‌ندرت اتفاق می‌افتد. از این رو پیچیدگی حالت‌میانگین الگوریتم‌ها همان رفتار مورد انتظار ماست. با استفاده از پیچیدگی الگوریتم‌ها، می‌توانیم آن‌ها را از نظر میزان کارایی با یکدیگر مقایسه کنیم. برای مثال، زمان اجرای الگوریتم‌های مرتب‌سازی ادغامی و مرتب‌سازی درجی را مقایسه می‌کنیم. می‌دانیم الگوریتم مرتب‌سازی ادغامی از مرتبه‌ی(O(log n و الگوریتم مرتب‌سازی درجی از مرتبه$n^{2}$ می‌باشد. همان‌طور که مشاهده می‌شود، برای مقادیر کوچک مانند ۱ یا ۲ الگوریتم مرتب‌سازی درجی سریع‌تر از الگوریتم مرتب‌سازی ادغامی عمل می‌کند اما هرچه مقدار n افزایش می‌یابد، الگوریتم مرتب‌سازی ادغامی بسیار سریع‌تر از الگوریتم مرتب‌سازی درجی عمل می‌کند؛ بنابراین از آنجا که اغلب برای ورودی‌های خیلی بزرگ از الگوریتم‌ها استفاده می‌کنیم، به تحلیل الگوریتم‌ها برای nهای بزرگ می‌پردازیم. در این مقاله سعی شده تا روش‌هایی برای مقایسه زمان اجرای الگوریتم‌ها بیان کنیم تا به درک روشنی از میزان بهینه بودن آن‌ها برسیم. در ابتدا به معرفی علایم قراردادی پرداخته سپس مفاهیم، تعاریف و مثال‌هایی از آن‌ها بیان می‌کنیم.

علایمی که ما از آن‌ها برای نشان دادن کران‌های مجانبی استفاده می‌کنیم، معرف توابعی هستند که به آنها توابع رشدمی‌گوییم و دامنه آن‌ها مجموعه‌ای از اعداد طبیعی است. این علایم عبارت‌اند از:

$\mathrm {O}$ : کران بالای مجانبی

${\Omega }$ : کران پایین مجانبی

${\theta }$ : کران دوطرف مجانبی

نماد $\mathrm {O}$

تعریف ریاضیاتی این نماد به شکل زیر می‌باشد:

$\mathrm {O} (g(n))=f(n):\exists \;c,n_{0}>0:0<f(n)<cg(n),\forall \;n>n_{0}$

یعنی آهنگ رشد تابع (g(n برای مقادیر بزرگ n، بیشتر یا مساوی آهنگ رشد تابع (f(nاست. در این‌صورت می‌گوییم(g(n کران بالای مجانبی برای (f(nاست.

به‌طور مثال:

$n^{2}=\mathrm {O} (n^{2})$

$n\log {n}=\mathrm {O} (n^{2})$ $nlogn=O(n^{2})$

نکته: منظور از$f=\mathrm {O} (g(n))$ در واقع $f\in \mathrm {O} (g(n))$ است.

نماد ${\Omega }$

تعریف ریاضیاتی این علامت به شکل زیر می‌باشد که در آن تابع(g(nکران پایین مجانبی برای تابع (f(nاست.

${\Omega }(g(n))=f(n):\exists \;c,n_{0}>0:0<cg(n)<f(n),\ \forall \;n>n_{0}$

به‌طور مثال:

${\sqrt {n}}={\Omega }(logn)$

$n^{3}={\Omega }(n^{2})$

نماد ${\theta }$

بیانگر کران دوطرف مجانبی است که به صورت زیر تعریف می‌شود:

${\theta }(g(n))=f(n):\exists \;c_{1}\ ,c_{2}\ ,\ n_{0}>0:0<c_{1}g(n)<f(n)<c_{2}g(n),\ \forall \;n>n_{0}$

این رابطه بدین معنی است که آهنگ رشدf و g برای مقادیر یزرگ n یکسان است و هیچ‌یک از این دو تابع از دیگری جلو نمی‌زنند.

به‌طور مثال زمان اجرای مرتب‌سازی درجی $an^{2}+bn+c$ است؛ بنابراین، $T(n)=\theta (n^{2})$، زیرا می‌توان به‌سادگی مقادیر مثبتی برای $c_{1}$ و $c_{2}$ یافت که $c_{1}n^{2}<an^{2}+bn+c<c_{2}n^{2}$.

مثال: ثابت کنید که $100n^{2}+5n-4\neq \theta (n^{3})$

اثبات: باید نشان داد که نمی‌توان مقادیر مثبتی برای $c_{1}$ ، $c_{2}$ و $n_{0}$ یافت که رابطهٔ $c_{1}n^{3}<100n^{2}+5n-4<c_{2}n^{3}$ برای همه مقادیر $n>n_{0}$ برقرار باشد. به‌وضوح به ازای هر مقدار $c_{1}>0$ و برای مقادیر بزرگ n $c_{1}n^{3}\nleq 100n^{2}+5n-4$.

لم: یک تابع چندجمله‌ای، از مرتبهٔ دقیق جملهٔ با بزرگترین توانش است. یعنی با فرض k>0 و$a_{k}>0$ داریم:

$a_{k}n^{k}+a_{k-1}n^{k-1}+...={\theta }(n^{k})$

نکته: طبق تعریف، ${\theta }(g(n))\subseteq {\mathrm {O} }(g(n))$.

همچنین تابع${\theta }$ در واقع عطف O و${\Omega }$ است به عبارت دیگر،

قضیه:شرط لازم و کافی برای $f(n)={\theta }(g(n))$ آن است که $f(n)=\mathrm {O} (g(n))$ و $f(n)={\Omega }(g(n))$.

خواص توابع رشد

خاصیت تراگذاری

تابع‌های رشد تعریف شده خاصیت تراگذاری دارند.

از$f(n)={\theta }(g(n))$ و$g(n)={\theta }(h(n))$ نتیجه می‌شود$f(n)={\theta }(h(n))$.

از$f(n)=\mathrm {O} (g(n))$ و$g(n)=\mathrm {O} (h(n))$ نتیجه می‌شود$f(n)=\mathrm {O} (h(n))$.

از$f(n)=\Omega (g(n))$ و$g(n)=\Omega (h(n))$ نتیجه می‌شود$f(n)={\Omega }(h(n))$.

خاصیت بازتابی

تابع‌های رشد تعریف شده خاصیت بازتابی دارند.

$f(n)={\theta }(f(n))$

$f(n)=\mathrm {O} (f(n))$

$f(n)={\Omega }(f(n))$

خاصیت تقارنی

تابع رشد${\theta }$ خاصیت تقارنی دارد.

$f(n)={\theta }(g(n))$ اگر و تنها اگر $g(n)={\theta }(f(n))$.

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

در تابع‌های رشد تعریف شده خاصیت تقارنی‌ترانهاده به‌صورت زیر وجود دارد:

شرط لازم و کافی برای $f(n)=\mathrm {O} (g(n))$ آن است که $g(n)={\Omega }(f(n))$.

منابع

• Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein، (Introduction to Algorithms(3rd.Editionنگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (رده)
• محمد قدسی، داده ساختارها و مبانی الگوریتم‌ها