زمان اجرای الگوریتم

زمان اجرای یک الگوریتم ((T(n) از مسائل مهم طراحی الگوریتم می‌باشد و غالباً کارایی الگوریتم ها، از روی زمان اجرای آن‌ها بررسی می‌شود. همان‌طور که می دانیم الگوریتم عبارتست از: مجموعه‌ای از دستورها و دستورالعمل‌ها برای حل مسئله، که شرایط زیر را باید دارا باشد:

• دقیق باشد
• مراحل ان به ترتیب اجرا شود
• پایان پذیر باشد

انواع زمان اجرا

زمان اجرا را با تابع O بزرگ محاسبه می‌کنند.

نوع	زمانT(n)	مثال
ثابت	O(1)	10
لگاریتمی	T(n) = O(log n)	log n, log(n^2)
چند لگاریتمی	T(n) = O((log n)^k)	^2(log n)
خطی	O(n)	n
مجذوری	O(n^2)	n^2
چند جمله‌ای	2^O(log n) = poly(n)	n, n log n, n^10
(زیر نمایی(تعریف اول	O(2^n^ε) for all ε > 0	O(2^log n^log log n)
(زیر نمایی(تعریف دوم	2^o(n)	2^n^1/3
نمایی	2^poly(n)	2^n, 2^n^2
فاکتوریل	O(n!)	n!
نمایی دوبل	2^2^poly(n)	2^2^n

روش محاسبه

الگوریتم‌ها توسط زبان‌های برنامه نویسی پیاده‌سازی می‌شوند و هر الگوریتم توسط یک برنامه ارائه می‌شود هر برنامه نیز مثل الگوریتم زمان اجرای خاص خود را دارد .عوامل دخیل در زمان اجرای برنامه:

• سرعت سخت افزار
• نوع کامپایلر
• اندازه داده ورودی
• ترکیب داده‌های ورودی
• پیچیدگی زمانی الگوریتم
• پارامترهای دیگر که تأثیر ثابت در زمان اجرا دارند.

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

برای محاسبه تابع (T(n برای یک الگوریتم موارد زیر را باید در محاسبات در نظر بگیریم:

• زمان مربوط به اعمال جایگزینی که مقدار ثابت دارند.
• زمان مربوط به انجام اعمال محاسباتی که مقدار ثابت دارند.
• زمان مربوط به تکرار تعدادی دستور یا دستورالعمل
• زمان مربوط به توابع بازگشتی

از موارد ذکر شده در محاسبه (T(n یک الگوریتم محاسبه تعداد تکرار عملیات و توابع بازگشتی اهمیت ویژه‌ای دارند و کا پیچیدگی زمانی مربوط به این دو می‌باشد.

مثال:تعداد کل مراحل برنامه زیر را محاسبه کنید.

 0                         (int func(int n
 ۰                                     }  
 0                            ;int i
 1                            ;int sum=۰
 FOR(i=1;i<=n;i++)                        n+1 
 sum=sum+i;                            n 
 1                             ;return sum                             
 0                                 {

کل عبارت مساوی 2n+3 می‌شود.همان طور که مشاهده می کنید زمان اجرای هر عبارت جایگزینی یا محاسباتی را مساوی ۱ واحد زمانی فرض می کنیم.هم چنین دستور داخل حلقه n بار انجام می‌شود ولی آزمایش کردن شرط حلقه در خط for به تعداد n+1 بار صورت می‌گیرد.دستور Return نیز مساوی یک واحد زمانی است.

• نکته

خطوط { } و نیز خط اول تعریف تابع و تعریف متغیر دستورهایی نیستند که توسط پردازنده اجرا شوند و زمان اجرای آن‌ها برابر صفر است.

• نکته

اگر عمل اصلی را فقط خط ;Sum=sum+I فرض کنیم انگاهT(n)=n خواهد بود.

مثال:دستور اصلی a=a+1 در قطعه برنامه زیر چند بار اجرا می گردد؟

                    (++For( i=1 ; i<=m ;i
            ( ++For(j=1 ; j<=n ; j
                 ; A=a+1

• نکته

حلقه‌های for برنامه مستقل از یکدیگر هستند

T(N)=MN

مثال: دستور اصلی a=a+1 در قطعه برنامه زیر چند بار اجرا می گردد؟

                     (++For(j=1 ; j<=n ; j  
          ++For( i=1 ; i<=j ;i
                  ;A=a+1

• نکته

حلقه‌های for برنامه به یکدیگر وابسته اند:

تعداد اجرا شدن A=a+1;	I	J
۱ بار	۱	۱
۲ بار	۱٬۲	۲
۳بار	۱٬۲،۳	۳
-	-	-
-	-	-
-	-	-
n بار	1,2،3,...,n	n

تعداد اجرا شدن دستور اصلی= 3,2،1,...,n(n+1)/2 = n

T(n)=n(n+1)/2

منابع

• بابا محمودی،رمضان. کتاب طلایی پویندگان دانشگاه تحلیل و طراحی الگوریتم ها.تهران:نشر ۱۳۹۰.
• احمدی، احمد. فایل در فایل. چاپ دوم. تهران: نشر۲، ۱۳۷۵