پیچیدگی الگوریتم‌ها و مرتبه‌ی توابع

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

فرض کنیم زمان اجرای الگوریتمی $5n^2+100n+4$ باشد. حال در تحلیل مجانبی از ضرایب ثابت صرف نظر کرده و زمان اجرای الگوریتم را $n^2$ فرض می‌کنیم. خوشبختانه این تقریب در اکثر موارد، تقریب معقولی می‌باشد زیرا ضرایب ثابت در الگوریتم‌ها اعداد کوچکی می‌باشند و زمان اجرا را چندان تحت تاثیر قرار نمی‌دهند.

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

همانطور که گفته شد، برای تحلیل الگوریتم‌ها از عوامل ثابت چشم‌پوشی می‌کنیم. برای بهتر انجام دادن این کار به نمادگذاری ویژه‌ای نیازمندیم. می‌گوییم تابع $f(n)$ از $O(g(n))$ است، اگر ثابت‌های $c$ و $N$ وجود داشته باشند، به گونه‌ای که برای $n\geq N$ داشته باشیم: $g(n)\leq cf(n)$. $O$ به صورت «اُ» یا «اُی بزرگ» تلفظ می‌شود. به عبارت دیگر برای $n$ های به قدر کافی بزرگ، تابع $g(n)$ از چند برابر تابع $f(n)$ بزرگ‌تر نیست. (در اینجا «چند» همان ضریب ثابت $c$ است.) نماد $O$ تابع را تنها از سمت بالا محدود می‌کند بنابراین تابع $f(n) = 5n^2+100n + 4$ هم از $O(n^2)$ و هم از $O(n^3)$ می‌باشد.

نماد $O$ بسیاری از پیچیدگی‌های توابع ریاضی را از بین می‌برد و از تمامی عوامل ثابت چشم‌پوشی می‌کند. برای مثال پایه‌ی لگاریتم در نماد O تاثیری ندارد: $$O(\log_{2} n) = O(4\log_{16} n) = O(\log_{16} n) = O(\log n) $$ اردر توابع ثابت نیز $O(1)$ محسوب می‌شود.

استفاده از نماد $O$ برای تحلیل الگوریتم‌ها روش معقولی می‌باشد، زیرا تفاوت زمان اجرا به ازای ورودی‌هایی با اندازه بزرگ صورت می‌گیرند و نماد $O$ سعی می‌کند تا میزان رشد توابع بر اساس اندازه ورودی (و نه چیزی بیشتر) را نشان بدهد. در شکل زیر رشد مقدار تابع $N=f(n)$ را به ازای توابع مختلف می‌توان مشاهده کرد.

• طراحی الگوریتم با رویکردی خلاقانه - یودی منبر - ترجمه‌ی احمد صادقی صفت و سید علی حسینی
• * پیچیدگی زمانی - ویکی‌پدیا