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

برای یک مسئله‌ی خاص در برنامه‌نویسی ممکن است الگوریتم‌های گوناگونی وجود داشته باشد و باید بکوشیم تا مناسب‌ترین آنها برگزیده شود. کارایی یک الگوریتم را می‌توان با دو معیار سنجید: الف) «مدت زمان لازم برای اجرای الگوریتم» و ب) «حافظه‌ی لازم برای اجرای الگوریتم». در بیشتر مواقع، معیار اصلی در ترجیح یک الگوریتم به الگوریتم‌های دیگر برای حل مسئله‌ای یکسان، مدت زمان اجرای آن است. در اینجا منظور از زمان، تعداد ثانیه یا هر واحد زمانی دیگر برای اجرای الگوریتم نیست، بلکه تخمینی است از تعداد عملیاتی که در هنگام اجرای یک الگوریتم انجام می‌شود.

مدت زمانی که الگوریتم برای اجرا نیاز دارد اغلب به اندازه‌ی ورودی آن وابسته است. برای مثال، مرتب‌سازی 10,000 عنصر نسبت به مرتب‌سازی 10 عنصر به زمان بیشتری نیاز دارد. میزان افزایش تعداد عملیات الگوریتم بر اثر افزایش اندازه‌ی ورودی آن «نرخ رشد الگوریتم» نامیده می‌شود. زمان اجرای یک الگوریتم، تابعی از اندازه‌ی ورودی آن است؛ اما به‌دست‌آوردن چنین تابعی دشوار و پیچیده است. بنابراین برای محاسبه‌ی اجرای الگوریتم از نوعی تقریب استفاده می‌شود که به ما کمک می‌کند تا تخمین بزنیم چه تعداد عملیات به ازای اندازه‌ی ورودی تابع انجام می‌شود. اگر n اندازه‌ی ورودی باشد، زمان اجرای الگوریتم بر حسب n را معمولاً با T(n) نمایش می‌دهیم.

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

الف) عبارات توضیحی: توضیحات، عبارات غیراجرایی هستند و تعداد گام‌های آنها صفر است.
ب) عبارات تعیین نوع: عباراتی هستند که برای معرفی متغیرها و ثابت‌ها و انواع جدید و ... می‌باشند و چون اجرایی نیستند، تعداد گام‌های آنها صفر است.
ج) عبارات و دستورات انتساب: تعداد گام هر دستور انتساب یک است به جز عبارتی که برای فراخوانی تابع است که برای آن باید گام‌های لازم برای اجرای تابع را محاسبه کنیم.
د) عبارات تکرار: شمارش را فقط برای قسمت کنترل این عبارات در نظر می‌گیریم. هنگامی که حلقه‌ی تکرار ابتدا شرط را بررسی کرده و سپس دستورات را اجرا می‌کند، اگر تعداد تکرار دستورات k بار باشد، تعداد تکرار قسمت کنترل حلقه، k+1 خواهد بود و هنگامی که در حلقه، ابتدا دستورات اجرا شوند و در آخر شرط بررسی گردند، برای k دستور، تعداد تکرار قسمت کنترل حلقه، k بار خواهد بود.
ه) عبارت نام تابع: تعداد گام این عبارت صفر است.
و) عبارت return: تعداد گام این عبارت یک است.

مثال: تعداد گام‌های تابع زیر چند است؟ (این تابع به زبان پایتون نوشته شده است و مجموع اعداد طبیعی از 1 تا n را محاسبه می‌کند.)

def sum(n):
    s = 0
    for i in range(1, n + 1):
        s += i
    return s

جواب:

خط	کد	تعداد گام
1	def sum(n):	0
2	s = 0	1
3	for i in range(1, n + 1):	1×(n+1)=n+1
4	s += i	1×n=n
5	return s	1
***	مجموع	2n+3

در کد بالا، در خط 1، نام تابع تعریف شده است که گام آن صفر است. در خط 2، یک عمل انتساب صورت گرفته است که گام آن 1 می‌باشد. در خط 3، عبارت تکراری داریم که n+1 بار اجرا می‌شود. خط 4، n بار داخل حلقه به اجرا درمی‌آید و خط 5 دارای گام 1 است. در مجموع، تعداد گام‌های این قطعه برنامه 2n+3 می‌باشد.

مثال: تعداد گام‌های قطعه برنامه زیر چند است؟

def count(n):
    s = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            s += i*j
    return s

جواب:

خط	کد	تعداد گام
1	def test(n):	0
2	s = 0	1
3	for i in range(1, n + 1):	1×(n+1)=n+1
4	for j in range(1, n + 1):	n×(n+1)=n2+n
5	s += i*j	n×n=n2
6	return s	1
***	مجموع	2n2+2n+3

در کد بالا، در خط 1، نام تابع تعریف شده است که گام آن صفر است. در خط 2، یک عمل انتساب صورت گرفته است که گام آن 1 می‌باشد. در خط 3، عبارت تکراری داریم که n+1 بار اجرا می‌شود. در خط 4، عبارت تکراری داریم که n(n+1) بار اجرا می‌شود. در خط 5، n×n بار مقدار حاصلضرب به انباره افزوده می‌گردد و خط 6 که خروجی تابع است دارای گام 1 است. در مجموع، تعداد گام‌های این قطعه برنامه 2n²+2n+3 می‌باشد.

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

$$T_{average}(n) = \sum_{i=1}^{m} {p_i t_i}$$

در این رابطه، n نشان‌دهنده‌ی اندازه‌ی ورودی، p_i احتمال رخداد دسته‌ی i اُم و t_i تعداد عملیات زمان مورد نیاز دسته‌ی i اُم است.

تحلیل پیچیدگی زمانی بدترین حالت الگوریتم جستجوی ترتیبی (خطی):
عمل مبنایی: مقایسه‌ی یک عنصر آرایه با x
اندازه‌ی ورودی: n (تعداد عناصر آرایه)
عمل مبنایی حداکثر n مرتبه انجام می‌شود و این حالتی است که x در آرایه وجود ندارد یا x آخرین عنصر آرایه است. بنابراین:

W(n) = n

تحلیل پیچیدگی زمانی حالت میانی الگوریتم جستجوی ترتیبی (خطی):
عمل مبنایی: مقایسه‌ی یک عنصر آرایه با x
اندازه‌ی ورودی: n (تعداد عناصر آرایه)
برای k به صورتی که 1<k<n، احتمال این که x عنصر k اُم آرایه باشد برابر با 1/n است. پیچیدگی زمانی حالت میانی برابر است با:

$$A(n) = \sum_{k=1}^{n} {(k × \frac{1}{n})} = \frac{1}{n} × \sum_{k=1}^{n}{k} = \frac{1}{n} × \frac{n(n+1)}{2} = \frac{(n+1)}{2}$$

تحلیل پیچیدگی زمانی بهترین حالت الگوریتم جستجوی ترتیبی (خطی):
عمل مبنایی: مقایسه‌ی یک عنصر آرایه با x
اندازه‌ی ورودی: n (تعداد عناصر آرایه)
از آنجایی که n>1 است، بنابراین باید حداقل یک گذر از حلقه وجود داشته باشد و اگر x اولین عنصر آرایه باشد، بدون توجه به مقدار اندازه‌ی ورودی n، تنها یک بار حلقه اجرا خواهد شد.

B(n) = 1