تجزیه و تحلیل الگوریتم ها
’’’ تجزیه و تحلیل یک
الگوریتم ’’’ ، عبارتست از تعیین مقدار منابع مورد نیاز (مانند
زمان و ظرفیت ذخیره سازی) برای اجرای آن . بیشتر
الگوریتم ها طوری طراحی شده اند که با ورودی هائی با طولهای دلخواه کار کنند. معمولاً‌میزان ’’’ کارایی’’’ یا ’’’ پیچیدگی ’’’ یک الگوریتم بصورت تابعی بیان می شود که
طول ورودی را به تعداد مراحل (’’’ پیچیدگی زمانی’’’) یا محل های ذخیره سازی (’’’ پیچیدگی فضائی یا حافظه’’’) مورد نیاز برای اجرای الگوریتم ارتباط می دهد.
تجزیه و تحلیل الگوریتم بخشی مهم از
تئوری پیچیدگی محاسباتی گسترده است که تقریبهای نظری را برای منابع مورد نیاز هر الگوریتم که مسئله ای محاسباتی را حل می کند، فراهم می نماید. این تقریب ها موجب دستیابی به اطلاعات معقول برای تحقیق در مورد الگوریتم های کارا می شود.
در تجزیه و تحلیل نظری الگوریتم ها، معمول این است که پیچیدگی آنها را بصورت ’’’ تقریبی’’’ asymptotic تخمین بزنیم. بعنوان مثال برای تخمین زدن تابع پیچیدگی ورودهایی که واقعا طولانی هستند، از نمادهای O
بزرگ ،
امگا و
تتا استفاده می گردد. مثلاً
جستجوی دودوئیدر (log(n» O ، یا به اصطلاح « در زمان
لگاریتمی »، مراحلی را طی می کند که متناسب با یک لگاریتم است. معمولا ً‌بدین دلیل از تخمین های تقریبی استفاده می شود، چون
اجراهای متفاوت یک الگوریتم یکسان ممکن است از نظر میزان کارایی با هم متفاوت باشند. اما کارایی دو اجرای «معقول» یک الگوریتم خاص توسط یک فاکتور ثابت چند برابر کننده که «ثابت پنهان» نامیده می شود، به یکدیگر مرتبط می شوند.
اندازه گیری دقیق (نه تقریبی) کارایی اجرایی الگوریتم را می توان محاسبه کرد، ولی این کار معمولاً نیازمند برخورد با موارد خاص در موقع اجرای الگوریتم است، که
مدل محاسباتی خوانده می شود.
یک مدل محاسباتی را می توان بصورت یک
کامپیوتر انتزاعی ، همانند
ماشین تورنیگ تعریف کرد، و یا با فرض این موضوع که اعمال خاصی در واحد زمان انجام می پذیرند، آنرا تعریف نمود. بعنوان مثال ، اگر مجموعه ای مرتب که
جستجوی دودوئی را در مورد آن بکار می گیریم دارای n عنصر باشد، و بتوانیم تضمین کنیم که در هر واحد زمان فقط یکبار می توان عمل
جستجوی دودویی را انجام داد، آنگاه حداکثر به واحد زمان احتیاج داریم تا پاسخ را بیابیم.
اندازه گیری های دقیق میزان کارایی اجرایی الگوریتمها، برای کسانی که حقیقتاً الگوریتم ها را اجرا کرده و مورد استفاده قرار می دهند، مفید هستند ، زیرا این اندازه گیری ها دقیق تر است و بنابراین آنان را قادر می سازد آگاهی یابند که چقدر زمان لازم است تا یک سری عملیات به اجرا در آید . برای برخی مردم ( مثلاً
برنامه نویسان) ، ثابت پنهان می تواند به معنای شکست یا موفقیت باشد.
تخمین میزان کارایی زمان اجرا بستگی به این دارد که ما هر مرحله را چگونه تعریف کنیم. برای اینکه این تجزیه و تحلیل معنی داشته باشد، باید تضمین کرد که زمان مورد نیاز برای اجرای یک مرحله توسط یک مقدار ثابت محدود شده است یعنی حد بالایی برای آن تعریف شده باشد. باید در اینجا دقت کرد؛ بعنوان مثال در برخی تجزیه و تحلیل ها ، جمع کردن دو عدد را یک مرحله به حساب می آورند. ممکن است در برخی شرایط این فرض مورد قبول نباشد. مثلاً ، اگر اعدادی که در یک محاسبه مورد استفاده قرار می گیرند، بدون ترتیب خاص و بطور اختیاری بزرگ باشند، دیگر نمی توان فرض کرد که عمل جمع به مدت زمانی ثابت احتیاج دارد (مقدار زمان مورد نیاز برای جمع دو عدد دو رقمی و دو عدد 1000 رقمی را به کمک کاغذ و قلم مقایسه نمایید.)
