پیچیدگی زمانی
باتوجه به نزدیکی بسیار زیاد مطالب این مبحث با پیچیدگی محاسباتی و نماد 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، Θ وΩ که در بخش بعدی با آنها آشنا می‌شویم، بیان می‌شود.
این متن اصلی مقاله‌است که از کتاب خاصی[1] و کتاب دیگری[2] و یک پانویس هم دارد *[3]
زمان اجرای الگوریتم
زمان اجرای یک الگوریتم از مسائل مهم طراحی الگوریتم است و غالباً کارایی الگوریتم‌ها را از روی زمان اجرای آنها بررسی می‌شود. همان‌طور که می‌دانیم الگوریتم عبارتست از: مجموعه‌ای از دستورها و دستورالعمل‌ها برای حل مسئله که شرایط زیر را باید دارا باشد:
- دقیق باشد
- مراحل ان به ترتیب اجرا شود
- پایان پذیر باشد
الگوریتم‌ها توسط زبان برنامه‌نویسی پیاده‌سازی می‌شوند و هر الگوریتم توسط یک برنامه ارائه می‌شود هر برنامه نیز مثل الگوریتم زمان اجرای خاص خود را دارد.
عوامل دخیل در زمان اجرای برنامه:
- سرعت سخت‌افزار
- نوع کامپایلر
- اندازه داده ورودی
- ترکیب داده‌های ورودی
- پیچیدگی زمانی الگوریتم
- پارامترهای دیگر که تأثیر ثابت در زمان اجرا دارند.
از این عوامل سرعت سخت‌افزار و نوع کامپایلر به صورت ثابت در زمان اجرای برنامه‌ها دخیل هستند. پارامتر مهم پیچیدگی زمانی الگوریتم است که خود تابعی از اندازه مسئله است. ترکیب داده‌های ورودی نیز با بررسی الگوریتم در شرایط مختلف قابل اندازه‌گیری است. در ادامه سعی در بررسی پیچیدگی زمانی الگوریتم خواهیم داشت. برای بررسی الگوریتم تابعی به نام (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+۱)/۲ = n
T(n)=n(n+1)/2
پیچیدگی حافظه
پیچیدگی حافظه‌ای میزان فضائی از حافظه‌است که برنامه برای اجرای کامل به آن نیاز دارد. فضای مورد نیاز در هربرنامه مجموع قسمت‌های زیر است:[4]
- بخش ثابت فضا که معمولاً شامل فضای دستورالعمل، فضای متغیرهای با اندازه ثابت و فضای لازم برای ذخیره ورودی و خروجی‌های برنامه‌است.
- بخش متغیر فضا شامل فضای پشته و فضای موردنیاز برای مقادیر متغیرهایی که اندازه آنها بستگی به مسئله و مشخصات ورودی دارد.
در تحلیل فضای لازم روی تخمین بخش متغیر تأکید نداریم زیرا برای هر مسئله ابتدا باید مشخصات موردی را تعیین کنیم که کار دشواری است.
نمایش پیچیدگی الگوریتم
برای نمایش پیچیدگی الگوریتم‌ها از تعاریف زیر استفاده می‌شود:
Big-O (حدبالا)
تابع f(n) را برای n≥۰ در نظر بگیرید. می‌گوئیم((f(n) = O(g(n) است اگر ثابت مثبت و حقیقی c و عدد صحیح و غیر منفی N وجود داشته باشند به طوریکه به ازای تمام مقادیر n≥N:
f(n)≤cg(n) برقرار باشد.
این نماد حد بالائی برای تابع (f(n می‌دهد و وقتی بکار می‌رود که رفتار الگوریتم بدترین حالت و بیشترین زمان اجرا را برای مقادیرمعین ورودی دارد.
امگا/Ω (حدپائین)
تابع (f(n را برای n≥۰ در نظر بگیرید. می‌گوئیم ((f(n) = Ω(g(n) اگر ثابت مثبت و حقیقی c و عدد صحیح و غیر منفی N وجود داشته باشند به طوریکه به ازای تمام مقادیر n≥N:
((f(n) ≥ c(g(n) برقرار باشد.
این نماد حد پائینی برای تابع (f(n می‌دهد و وقتی بکار می‌رود که رفتار الگوریتم بهترین حالت و کمترین زمان اجرا را برای مقادیر معین ورودی دارد.
تتا/Θ (حدمتوسط)
تابع (f(n را برای n≥۰ در نظر بگیرید. می‌گوئیم((f(n) = Θ(f(n) است اگر ثابت‌های مثبت و حقیقی c و d و عدد صحیح غیر منفی N وجود داشته باشند به طوریکه به ازای تمام مقادیر n≥N:
c g(n) ≤f(n) ≤ d g(n) برقرار باشد.
به عبارت دیگر برای تابع پیچیدگی مفروض (f(n:
Θ(f(n)) = O(f(n)) ∩ Ω(f(n))
این نماد حدمتوسطی برای تابع(f(n می‌دهد و زمان اجرای الگوریتم را به صورت میانگینی از تعداد عملیات انجام شده با کلیه نمونه ورودی‌های مسئله نشان می‌دهد.
اگر زمان الگوریتم وابسته به ورودی نباشد با نماد O(۱) نشان داده می‌شود؛ و برای تحلیل الگوریتم باید به اندازه کافی الگوریتم را درک کرده باشیم تا بهترین و بدترین رفتار را تولید و محاسبه کنیم.
چون برآورد رفتار آماری ورودی‌ها امری دشوار است، در اکثر موارد به بدترین حالت قناعت می‌کنیم.
نکته. اگر الگوریتم شامل بخش‌های مختلفی باشد که هر قسمت پیچیدگی متفاوتی دارد، مرتبه بزرگی هر قسمت را پیدا کرده و بزرگترین مرتبه را به عنوان پیچیدگی کل الگوریتم در نظر می‌گیریم.
غالباً پیچیدگی (g(n یکی از توابع زیر است: n (پیچیدگی خطی)، log n (لگاریتمی)، n^a (چندجمله‌ای) و a^n که a≥۲ (نمائی).
در زیر مربته اجرائی چند تابع به ترتیب صعودی نوشته شده‌است.
O(1) < O(n) < O(n ^ 3) < O(2 ^ n)
بهبود پیچیدگی یک برنامه
الگوریتم‌ها بر دو مبنای صرفه جویی در زمان، صرفه جویی در هزینه و استفاده از حافظه استوارند که اولی تحت عنوان پیچیدگی زمانی و دومی تحت عنوان پیچیدگی حافظه از آن یاد می‌شود که به ترتیب هر دو مستقل از سخت‌افزار و نوع زبان برنامه‌نویسی است و بر این اصل استوار است که دستور کلیدی الگوریتم (دستوری که در تمام تکرارهای الگوریتم وجود دارد) به ازای مقادیر گوناگون پارامتر ورودی در بدترین حالت، بهترین حالت و حالت میانگین حداقل یا حداکثر یا به‌طور متوسط چندبار اجرا می‌شوند یا چه میزان حافظه را به خود تخصیص می‌دهند.[5]
بنابراین روش‌های گوناگونی طراحی شده‌است تا به کمک آنها الگوریتم‌هایی نوشته و براساس آنها برنامه‌نویسی‌هایی انجام گیرد تا بهترین کارایی از لحاظ پیچیدگی زمانی و مکانی حاصل شود که روش‌های زیر از جمله مهم‌ترین آنها بوده و در کتب طراحی الگوریتم مورد بحث قرار گرفته‌است:
- روش تقسیم و غلبه
- برنامه‌نویسی پویا
- روش حریصانه
- روش عقبگرد
- روش شاخه و حد
برای محاسبه پیچیدگی روابط می‌توانید از قضایای زیادی استفاده نمایید که مهم‌ترین آنها قضیه اصلی(قضیه اصلی واکاوی الگوریتم‌ها) است که بسیار کارآمد است و در[6] کتابمقدمه‌ای بر الگوریتم‌ها به وضوح توضیح داده شده‌است.
برای آنکه مشخص کنیم میزان کارایی یک الگوریتم در حل یک مسئله تا چه حد است باید به تحلیل آن بپردازیم.
تحلیل پیچیدگی زمانی
هنگامی که کارایی الگوریتم‌ها را بر حسب زمان تحلیل می‌کنیم، تعداد چرخه‌های واقعی CPU را تعیین نمی‌کنیم، زیرا این به کامپیوتر خاصی که الگوریتم روی آن اجرا می‌شود بستگی دارد. در عوض به معیاری نیاز داریم که مستقل از کامپیوتر، زبان برنامه‌نویسی، برنامه‌نویس و خلاصه همه جزئیات الگوریتم از قبیل افزایش اندیس حلقه‌ها و غیره باشد. به‌طور کلی تحلیل پیچیدگی زمانی یک الگوریتم عبارت است از تعیین تعداد دفعاتی که عمل اصلی به ازای هر مقدار از اندازه ورودی انجام می‌شود.
به کار بستن نظریه:
هنگام به کار بستن نظریه تحلیل الگوریتم‌ها، گاهی باید از زمان لازم برای اجرای عمل اصلی دستورهای سربار و دستورهای کنترلی روی کامپیوتری که الگوریتم را اجرا می‌کند آگاه باشیم. منظور از دستورهای سربار دستوراتی نظیر مقدار دهی اولیه پیش از شروع حلقه هاست. تعداد دفعاتی که این دستورها اجرا می‌شوند با تعداد ورودی افزایش نمی‌یابد.
تحلیل درستی الگوریتم:
به معنای تحلیل کارایی بر حسب زمان یا حافظه است.
جستارهای وابسته
منابع
- بابا محمودی، طلایی پویندگان دانشگاه تحلیل و طراحی الگوریتم‌ها، ۱۱۵–۱۵۰. [=صفحات کتاب]
- احمدی، فایل در فایل.
- این یک پانویس توضیحی‌است.
- برگرفته از کتاب ریاضیات گسسته و کاربردهای آن، کنت اچ روزن
- برگرفته از مباحث کارشناسی ارشد مهندسی کامپیوتر (طراحی الگوریتم)
- introduction to algorithms by CLRS
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Kenneth H. Rosen, Discrete Mathematics and Its Applications 5th ed. McGraw Hill.
Jalal Marhon Almaa - Time Travel E-Book