✤  پیچیدگی زمانی اجرای الگوریتم

زمانی که برای حل یک مسئله الگوریتم طراحی می‌کنیم یا قصد استفاده از یک الگوریتم از پیش ابداع شده را داریم، عموما برایمان مهم است بدانیم کارآیی الگوریتم چگونه است و تا چه حد می‌توان روی آن حساب باز کرد. به ویژه اگر برای حل یک مسئله بیش از یک الگوریتم موجود باشد، باید بتوان آنها را به نحوی با هم مقایسه کرد. گاهی چنین مقایسه‌ای بر اساس قابلیت پیاده‌سازی یا میزان سادگی پیاده‌سازی است. اما در بسیاری مواقع سرعت تولید خروجی الگوریتم بسیار مهمتر از پیچیدگی پیاده‌سازی یا مدت زمان مورد نیاز برای پیاده‌سازی است. به همین دلیل طراحی یک الگوریتم کارا بسیار مهم است و در مسابقات برنامه‌نویسی همچون ACM-ICPC نیز این توانایی محک می‌خورد. در کنار این موضوع، ممکن است میزان حافظه‌ی مورد نیاز هم مهم باشد.

یک راه ساده برای مقایسه‌ی کارایی دو الگوریتم، پیاده‌سازی هر دو و بررسی زمان اجرا با ورودی‌های یک شکل است! این روش در عمل همواره ممکن نیست. دلیل اول آن است که در چنین حالتی باید سعی کنیم برنامه‌های الگوریتم‌ها را به بهترین حالت ممکن پیاده‌سازی کنیم و صرفا دغدغه‌ی کارایی الگوریتم را داشته باشیم. این شرط همواره مهم است و زمانی که کارایی دو الگوریتم بررسی می‌شود، به شرط پیاده‌سازی درست آنها است. چرا که یک پیاده‌سازی بد نتیجه‌ی استفاده از الگوریتم خوب را از بین می‌برد. اما هر پیاده‌سازی همواره با ابهام بهینه بودن همراه است و نمی‌توان مطمئن بود بهترین پیاده‌سازی ممکن است. مخصوصا اگر الگوریتم مورد نظر پیچیده باشد. از سوی دیگر، به صرف چند ورودی مشخص و نتایج آنها نمی‌توان از عملکرد کل الگوریتم مطمئن شد. ممکن است برای یک ورودی کوچک و حتی نه چندان کوچک یک الگوریتم بهتر از دیگری اجرا شود و اگر اندازه‌ی ورودی بزرگتر شود، نتیجه برعکس گردد یا حتی تغییرات متناقضی داشته باشند. یا آنکه ممکن است به ازای برخی ورودی‌ها زمان بسیار زیادی برای تولید خروجی نیاز باشد که در عمل آن میزان انتظار مقرون به صرفه نیست.

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

  

مفهوم پیچیدگی زمانی

  [برگرد بالا]

یک روش برآورد کارایی الگوریتم، شمارش تعداد عملیات اصلی مورد نیاز تا رسیدن به خروجی است. قطعه کد ساده‌ی زیر را در نظر بگیرید که مجموع اعداد $1$ تا $n$ را محاسبه می‌کند.

  

  

اگر خط اول کد را بخش اول، سه بخش حلقه‌ی for را بخش‌های دو تا چهار و خط بدنه‌ی حلقه را بخش پنجم در نظر بگیریم، بخش یک و دو تنها $1$ بار، بخش سه $ n + 1 $ بار و بخش‌های چهار و پنج هر کدام $n$ بار اجرا می‌شوند. پس در مجموع $3n+3$ عمل جمع، ضرب، مقایسه یا انتساب انجام می‌شود.

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

آنچه که در تحلیل عملکرد الگوریتم برای ما اهمیت دارد، میزان تغییر عملیات اصلی با بزرگ شدن اندازه‌ی ورودی است. مثلا اگر اندازه‌ی ورودی را $10$ برابر کردیم، چند برابر بیشتر باید منتظر تولید خروجی نسبت به حالت اولیه باشیم؟ در چنین شرایطی می‌توانیم از هر پارامتری که مستقل از اندازه‌ی ورودی مسئله است صرف نظر کنیم. مثلا در عبارت $3n+3$ جمع شدن با عدد $3$ امری مستقل از میزان بزرگی $n$ است و برای مقادیر بزرگ $n$ نیز این جمع تغییر چندانی در عدد نهایی ایجاد نمی‌کند. پس می‌توان از این ضریب ثابت صرف نظر کرد و تنها $3n$ را در نظر گرفت.

قطعه کد دیگری در نظر بگیرید که تعداد اعمال اصلی آن $9n-2$ باشد. بر اساس توضیحات قبلی تحلیل کارآیی این تعداد عملیات با تحلیل $9n$ تفاوتی ندارد. وجه مشترک $3n$ و $9n$ آن است که رشد خطی بر اساس تغییر $n$ دارند. در رشد خطی میزان رشد عملیات اصلی مستقل از ضریب $n$ و برابر با میزان رشد اندازه‌ی ورودی است.

این تفاسیر نشان از آن دارد که می‌توان $3n$ و $9n$ را از یک خانواده‌ی پیچیدگی زمانی دانست. به همین دلیل نیز در بخش پنجم قطعه کد فوق، تعداد کل تکرار دو دستور جمع و انتساب را به جای $2n$ تنها $n$ در نظر گرفتیم. چون این دو از یک خانواده هستند و در نهایت ضریب را می‌توان کنار گذاشت. ساده‌ترین عضو این خانواده $n$ است که به عنوان نماینده‌ی خانواده مطرح می‌شود. این نماینده را می‌توان با یک نماینده‌ی دیگر مانند $n^2$ به جای چندجمله‌هایی همچون $n^2-1000$ مقایسه کرد و نتیجه گرفت الگوریتمی از خانواده‌ی اول برای حل یک مسئله کاراتر از الگوریتمی از خانواده‌ی دوم برای حل همان مسئله است. چون $10$ برابر شدن اندازه‌ی ورودی، تاثیر $10$ برابری در زمان تولید خروجی خانواده‌ی اول و تاثیر $100$ برابری در زمان تولید خروجی خانواده‌ی دوم دارد. هر کدام از این خانواده‌ها یک مرتبه‌ی زمانی اجرا (یا حافظه‌ی مصرفی) هستند که با عنوان پیچیدگی زمانی (یا حافظه‌ی مصرفی) نیز شناخته می‌شوند.

در یک چندجمله‌ای مانند $6n^3-7n^2+4n-2$ عبارتی از درجات مختلف $n$ وجود دارد. ما زمانی که در مورد پیچیدگی زمانی صحبت می‌کنیم، منظورمان برای مقادیر به اندازه‌ی کافی بزرگ ورودی است. اگرنه برای مقادیر کوچک، عموما تمام الگوریتم‌ها در زمان قابل قبولی خروجی را تولید می‌کنند و دغدغه‌ای از بابت کارایی الگوریتم نداریم. به همین دلیل در چنین عبارتی جمله با رشد بیشتر مؤثرترین بخش است و عبارت در آن مرتبه‌ی پیچیدگی قرار می‌گیرد. یعنی چندجمله‌ای $6n^3-7n^2+4n-2$ از خانواده‌ی $n^3$ است و عبارت $ \frac{1}{1000}2^n+1000n^{10} - 7n + 3$ از خانواده‌ی $2^n$.

ممکن است این سوال مطرح شود که نقش ضریب را چگونه می‌توان تفسیر کرد؟ طبیعتا اگر یک الگوریتم از مرتبه‌ی $n$ و الگوریتم دیگری از مرتبه‌ی $n^3$ باشد، الگوریتم اول بسیار کاراتر است. اگر هر دو از یک مرتبه باشند، این ضریب‌ها هستند که سرعت رسیدن به جواب را مشخص می‌کنند. اما اگر این دو الگوریتم روی دو سیستم مجزا اجرا شوند، ضرایب لزوما راهنمای درستی نخواهند بود. به عنوان مثال، دو الگوریتم را در نظر بگیرید که به ترتیب $10n$ و $100n$ عمل اصلی دارند و روی دو سیستم متفاوت اجرا می‌شوند که سرعت پردازش دومی $100$ برابر بیشتر است. در چنین حالتی الگوریتم دوم $10$ برابر سریع‌تر از الگوریتم اول به نتیجه می‌رسد! ولی باز هم وجه مشترک آن دو این است که $k$ برابر شدن اندازه‌ی ورودی، زمان تولید خروجی را نیز تقریبا $k$ برابر می‌کند. در مقابل، فرض کنید الگوریتم دوم $n^2$ عمل اصلی داشته باشد. اگر اندازه‌ی ورودی $1000$ برابر شود، زمان تولید خروجی الگوریتم اول در سیستم کندتر نیز $1000$ برابر خواهد شد. اما این زمان برای الگوریتم دوم $1$ میلیون برابر می‌شود که بالا بودن سرعت پردازنده‌ی سیستم اجرایی آن نیز چندان کمکی به تولید خروجی در زمان نزدیک به الگوریتم اول روی سیستم کندتر نمی‌کند.

تذکر: در محاسبات پیچیدگی زمانی الگوریتم، هر ضریبی ضریب نیست! اگرچه $n$ و $\frac{n}{2}$ از یک خانواده هستند؛ اما $2^n$ و $2^{\frac{n}{2}}$ دو خانواده‌ی جدا از همند. عبارت دوم را می‌توان به صورت $\sqrt{2}^n$ نوشت و میزان رشد آن دو را مقایسه کرد.

  

پیچیدگی زمانی در بهترین و بدترین حالت

  [برگرد بالا]

در قطعه کد قبلی هر اجرا تعداد مشخصی عمل اصلی وابسته به $n$ داشت. اما برنامه‌ها لزوما از چنین الگوریتم‌هایی ساخته نمی‌شوند. تابع زیر را در نظر بگیرید که در $n$ عنصر اول آرایه‌ی arr مقدار x را جستجو کرده و اندیس آن را باز می‌گرداند.

  

  

در فرآیند جستجو ممکن است عنصر مورد نظر در هر یک از خانه‌های آرایه باشد یا اصلا وجود نداشته باشد که مقدار $-1$ توسط تابع بازگردانده می‌شود. بنابراین نمی‌توان رابطه‌ی ثابت و مشخصی برای تعداد اعمال اصلی تعریف کرد. در چنین شرایطی می‌توان گفت بهترین حالت اجرا از مرتبه‌ی $1$ است و بدترین حالت آن از مرتبه‌ی $n$. مرتبه‌ی $1$ مستقل بودن زمان اجرا از اندازه‌ی ورودی را مشخص می‌کند. عنصر مورد نظر چه در ابتدای یک آرایه با $10$ عنصر باشد و چه در ابتدای یک آرایه با $10^{100}$ عنصر، یافتن آن تنها یک مقایسه نیاز دارد و در زمان ثابتی اتفاق می‌افتد.

  

پیچیدگی زمانی متوسط الگوریتم

  [برگرد بالا]

دو حالت بهترین و بدترین ممکن است کم اتفاق بیفتند. محاسبه‌ی مرتبه‌ی بدترین حالت این حسن را دارد که نهایت منابع یا زمان مورد نیاز را برآورد می‌کنیم. اما عموما اجرا به ازای ورودی‌های مختلف به این میزان زمان یا حافظه نیاز ندارد. به همین دلیل حالت متوسط اجرا نیز محاسبه می‌شود تا بدانیم به طور متوسط الگوریتم در چه پیچیدگی زمانی سیر می‌کند.
حالت متوسط اجرا را می‌توان از محاسبه‌ی امید ریاضی به دست آورد. در مورد تابع جستجوی خطی فوق، با احتمال $\frac{1}{n}$ تعداد $i$ مقایسه (مقایسه تا خانه‌ی $i$ آرایه) ما را به جواب می‌رساند و امید ریاضی به ترتیب زیر محاسبه می‌شود.

\[ 1 \times \frac{1}{n} + 2 \times \frac{1}{n} + 3 \times \frac{1}{n} + \cdots + n \times \frac{1}{n} = ( 1 + 2 + 3 + \cdots + n) \times \frac{1}{n} \] \[ = \frac{n(n+1)}{2} \times \frac{1}{n} = \frac{n + 1}{2} = \frac{n}{2} + \frac{1}{2}\]

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

یک مثال دیگر روش حل مسئله‌ی برج هانوی است. برای جابجا کردن $n$ دیسک از میله‌ی مبدأ به میله‌ی مقصد ابتدا نیاز است $n-1$ دیسک بالایی را به میله‌ی کمکی منتقل کرده، سپس دیسک بزرگ را به میله‌ی مقصد برده و در نهایت دیسک‌های موجود در میله‌ی کمکی را به میله‌ی مقصد منتقل کنیم. اگر $T(n)$ تعداد حرکات مورد نیاز برای حل کامل مسئله باشد، بر اساس این توضیح می‌توان نوشت:

\[ T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1)+1, \quad T(1) = 1 \]

حل این رابطه‌ی بازگشتی به $T(n) = 2^n-1 $ می‌رسد. پس حل این مسئله از مرتبه‌ی پیچیدگی $2^n$ است. این مسئله بهترین و بدترین حالت ندارد و همواره یک رابطه برای آن برقرار است و نمی‌توان الگوریتم کاراتری نیز برای آن نوشت. پس می‌توان نتیجه گرفت به ازای مقادیر بزرگ $n$ حل آن بسیار زمانبر خواهد بود. به همین دلیل نیز از آن افسانه ساخته‌اند!

نکته‌ی آخر: در نوشته‌ی فوق همواره از ورودی‌های به اندازه‌ی کافی بزرگ بحث شده است. به عبارت دیگر ممکن است برای مقادیر کوچک ورودی، الگوریتمی با مرتبه‌ی بزرگتر بهتر جواب دهد. از سوی دیگر در برخی از مسائل اندازه‌ی ورودی محدودیت دارد و می‌توان برای آن حداکثر قائل شد. در چنین شرایطی ممکن است یک الگوریتم از مرتبه‌ی بزرگ هم کارایی خوبی داشته باشد. اگر پیاده‌سازی چنین الگوریتمی نیز ساده باشد، بهتر است از آن استفاده شود. نمونه‌ای از چنین مسائل مسئله‌ی آسانسورها از سوالات مسابقات برنامه‌نویسی ACM-ICPC است.