کارایی الگوریتم‌ها

از ویکی‌پدیا، دانشنامهٔ آزاد.

در نظریه پیچیدگی محاسباتی، الگوریتم‌ها از حیث کارایی در استفاده از منابعی مانند زمان و فضا (حافظه) مورد بررسی قرار می‌گیرند. در این بررسی آن چه اهمیت دارد میزان زمان و فضای مورد نیاز برای حل یک مساله‌ٔ خاص نیست بلکه چگونگی افزایش میزان زمان و فضای مورد نیاز با بزرگ شدن ورودی الگوریتم مورد توجه است.

مثلا فرض کنید دو الگوریتم الف و ب برای حل مساله‌ی زیر پیشنهاد شده‌اند. در این مساله نقشه‌ٔ یک منطقه شامل شهرهای قرار گرفته در آن منطقه، جاده‌های بین آن‌ها و طول هر جاده و نیز نام دو شهر مبدا و مقصد داده شده است. هدف پیدا کردن کوتاه‌ترین مسیر از مبدا به مقصد است.

فرض کنید به صورت تجربی مشاهده می‌کنیم که اگر تنها یک شهر به تعداد شهرهای نقشه اضافه شود الگوریتم الف به دو برابر زمان برای حل مساله نیاز دارد در حالی که زمان مورد نیاز برای الگوریتم ب وقتی دو برابر می‌شود که تعداد شهرهای نقشه دو‌ برابر شده باشد. بدیهی است که در چنین شرایطی الگوریتم ب را کاراتر از الگوریتم الف می‌دانیم.

در نظریه پیچیدگی محاسباتی نیز همین روش را پی‌می‌گیریم ولی به جای روشهای تجربی از روشهای ریاضی استفاده می‌کنیم. به این منظور ابتدا برای ورودی مساله یک سایز تعریف می‌کنیم. این سایز می‌تواند میزان حافظه‌ٔ مورد نیاز برای ذخیره‌ کردن ورودی مساله باشد. سپس زمان (یا فضای) مورد نیاز برای حل مساله توسط یک الگوریتم به صورت تابعی از سایز مساله محاسبه می‌شود. به محاسبه‌ یا تقریب زدن این چنین تابعی تحلیل الگوریتم گفته می‌شود.

اگر تابع به دست آمده به روش فوق چندجمله‌ای یا کوچک‌تر از یک چند‌جمله‌ای باشد الگوریتم را کارا و در غیر این ‌صورت آن را ناکارا می‌نامیم.