![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/Comparison_computational_complexity.svg/langfa-640px-Comparison_computational_complexity.svg.png&w=640&q=50)
تحلیل الگوریتمها
From Wikipedia, the free encyclopedia
موضوع تحلیل الگوریتمها تعیین میزان منابعی است که برای اجرای هر الگوریتم لازم است. منابعی مثل زمان، حافظه، پهنای باند ارتباطی، یا سختافزار رایانه در نظر گرفته میشوند. اکثر الگوریتمهای طراحی شده برای کار با ورودیهای با طول اختیاری تولید میشوند. کارایی یا پیچیدگی هر الگوریتم را با تابعی نشان میدهند که تعداد مراحل لازم برای اجرای الگوریتم را برحسب طول داده ورودی، یا میزان محلهای گرفته شدهٔ حافظه را بر حسب طول داده ورودی نشان میدهد. پیچیدگی زمانی، مقدارپیچیدگی محاسباتیای را توصیف میکند که در اجرای یک الگوریتم مصرف میشود. غالباً مشاهده میشود که یک مسئله را با استفاده از چندین تکنیک مختلف میتوان حل نمود ولی فقط یکی از آنها به الگوریتمی منجر میشود که از بقیه سریعتر است.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Binary_search_vs_Linear_search_example_svg.svg/220px-Binary_search_vs_Linear_search_example_svg.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/Comparison_computational_complexity.svg/320px-Comparison_computational_complexity.svg.png)
در تجزیه و تحلیل نظری الگوریتم آنچه مشترک است، برآورد پیچیدگی در معنای تقریبی آن است. به عنوان مثال، برآورد تابع پیچیدگی برای ورودی خودسرانه بزرگ. نمادهای برای این منظور استفاده میشوند. مثلاً گفته میشود، جستجوی دودویی به اجرا در
مرحله تناسب دارد.
معمولاً تخمینهای تقریبی استفاده میشوند، چرا که پیادهسازیهای مختلف از همان الگوریتم، ممکن است در کارایی متفاوت باشد. با این حال بازده هر دو، با «منطق» پیادهسازی یک الگوریتم داده شده، ضرب در یک ضریب ثابت به نام ثابت مخفی مرتبط است.
در مورد تحلیل الگوریتم باید در مورد موضوعاتی مانند تابع رشد، روش تحلیل الگوریتمهای ترتیبی و بازگشتی، حل رابطههای بازگشتی ساده، همگن و نا همگن و همچنین تحلیل سرشکنی صحبت کرد.