پیچیدگی زمانی

باتوجه به نزدیکی بسیار زیاد مطالب این مبحث با پیچیدگی محاسباتی و نماد O بزرگ توصیه می‌شود ابتدا مطالب مربوط به آنها

مطالعه شود و سپس برای مطالعهٔ دقیق تر موضوع ادامهٔ این مبحث را مطالعه نمایید.

ارزیابی کارائی الگوریتم‌ها

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

الگوریتم‌ها داشته باشیم.

ارزیابی در دو مرحله انجام می‌شود:

• آنالیز کارائی

• اندازه گیری کارائی

آنالیز کارائی یک تخمین اولیه‌است با دو معیار:

• پیچیدگی زمانی time complexity

• پیچیدگی حافظه space complexity

سنجیده می‌شود؛ که رفتار الگوریتم را در زمان اجرا با مجموعه‌ای از ورودی‌های منتخب توصیف می‌کنند.

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

آوری می‌شود.

پیچیدگی زمانی

زمان اجرای یک برنامه به موارد زیر بستگی دارد

• سخت‌افزار

• سیستم‌عامل

• کمپایلر

• نوع الگوریتم

• آرایش داده‌های ورودی

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

منظور از واحد زمانی، واحدهای زمانی واقعی مانند میکرو یا نانو ثانیه نمی‌باشد بلکه منظور واحدهای منطقی است که رابطه بین بزرگی (n) یک فایل یا یک آرایه و زمان مورد نیاز برای پردازش داده‌ها را شرح می‌دهد.(توجه کنید که هر دستور یک واحد زمانی اشغال می‌کند.)

مثلاً دستورات ;a=b و;c/d-e*; a=b هر کدام یک واحد زمانی را دربردارند.

مجموع تعداد عملکردهای اجرایی، زمان اجرای برنامه را می‌رساند و مستقل از ماشین است.

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

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

return (a+b-c) / (a+b)+۴٫۰ ;

بنابراین تعداد مراحل برای هر عبارت یک برنامه بستگی به ;نوع عبارت دارد، بطوریکه در عبارات توضیحی برابر صفر و در دستور انتسابی

بدون فراخوانی برابر یک می‌باشد. و در دستورات غیربازگشتی حلقه for، while، repeat until به تعداد تکرار حلقه در نظر گرفته می‌شود.

هدف از محاسبه پیچیدگی زمانی یک الگوریتم این است که بفهمیم نیازمندی یک الگوریتم به زمان با چه تابعی رشد می‌کند و هدف اصلی بدست

آوردن این تابع رشد است.

برای مثال هرچه زبان برنامه نویسی(مترجم (رایانه)) به زبان ماشین نزدیک تر باشد، برنامه با سرعت بیشتری به جواب خواهد رسید

زمان اجرا مقدار زمانی از کامپیوتر است که برنامه برای اجرای کامل مصرف می‌کند.

برای محاسبه پیچیدگی زمان الگوریتم ابتدا تعداد قدم‌های الگوریتم به صورت تابعی از اندازه مسئله مشخص می‌شود، برای انجام این کار

تعداد تکرارعملیات اصلی الگوریتم محاسبه می‌شود و به صورت تابع f بیان می‌شود. سپس تابع g، که مرتبه بزرگی تابع f را وقتی اندازه

ورودی به اندازه کافی بزرگ است نشان می‌دهد، بدست می‌آید. در نهایت پیچیدگی الگوریتم برای نشان دادن رفتار الگوریتم با ورودی‌های

مختلف

با استفاده از نمادها O، Θ وΩ که در بخش بعدی با آنها آشنا می‌شویم، بیان می‌شود. این متن اصلی مقاله‌است که از کتاب خاصی و کتاب دیگری و یک پانویس هم دارد *

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

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

• دقیق باشد

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

• پایان پذیر باشد

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

عوامل دخیل در زمان اجرای برنامه:

• سرعت سخت افزار

• نوع کامپایلر

• اندازه داده ورودی

• ترکیب داده‌های ورودی

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

• پارامترهای دیگر که تاثیر ثابت در زمان اجرا دارند.

از این عوامل سرعت سخت افزار و نوع کامپایلر به صورت ثابت در زمان اجرای برنامه‌ها دخیل هستند. پارامتر مهم پیچیدگی زمانی الگوریتم است که خود تابعی از اندازه مسئله می‌باشد. ترکیب داده‌های ورودی نیز با بررسی الگوریتم در شرایط مختلف قابل اندازه گیری می‌باشد. در ادامه سعی در بررسی پیچیدگی زمانی الگوریتم خواهیم داشت. برای بررسی الگوریتم تابعی به نام (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
۰                                 {

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

•  ;نکته

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

•  ;نکته

اگر عمل اصلی را فقط خط ;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

== پیچیدگی حافظه کتابمقدمه‌ای بر الگوریتم‌ها به وضوح توضیح داده شده‌است.

برای آنکه مشخص کنیم میزان کارایی یک الگوریتم در حل یک مسئله تا چه حد است باید به تحلیل آن بپردازیم.

تحلیل پیچیدگی زمانی:

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

به کار بستن نظریه:

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

تحلیل درستی الگوریتم:

به معنای تحلیل کارایی بر حسب زمان یا حافظه است.

جستارهای وابسته

• نظریه پیچیدگی محاسباتی
• طراحی الگوریتم
• مهندسی الگوریتم

منابع

Introduction to Algorithms by Thomas H. Cormen، Charles E. Leiserson، Ronald L. Rivest، and Clifford Stein
Kenneth H. Rosen، Discrete Mathematics and Its Applications ۵th ed. McGraw Hill.