Table of Contents
درک کارایی الگوریتم ها برای مهندسان برای بهینه سازی عملکرد و استفاده از منابع ضروری است.این مقاله یک رویکرد روشن و گام به گام برای تجزیه و تحلیل بهره وری الگوریتم از طریق محاسبات و مثال ها فراهم می کند.
مقدمه ای بر کارایی الگوریتم
بهره وری الگوریتم اندازه گیری می کند که چگونه مصرف زمان یا منابع یک الگوریتم با اندازه ورودی، به مقایسه الگوریتم های مختلف و انتخاب مناسب ترین آن برای یک مشکل خاص کمک می کند.
مرحله 1: شناسایی عملیات پایه
عملیات بنیادی را که به طور قابل توجهی بر زمان اجرای الگوریتم تأثیر می گذارد، مانند مقایسه، تکالیف یا محاسبات محاسباتی، محاسبه کنید که چقدر این عملیات نسبت به اندازه ورودی رخ می دهد.
مرحله ۲: عملیات اکسپرس به عنوان تابع اندازه ورودی
تعداد کل عملیات های اساسی را به عنوان تابع اندازه ورودی فرمول بندی کنید، به عنوان n. برای مثال، یک حلقه در حال اجرا n بار یک جزء خطی را دربر می گیرد، در حالی که حلقه های لانه ممکن است به چهار برابر یا بالاتر از شرایط سفارش کمک کنند.
مرحله 3: ساده سازی عملکرد با استفاده از بزرگ O Notation
کاهش عملکرد به اصطلاح غالب آن برای بیان کارایی الگوریتم با استفاده از بزرگ Onotation.برای مثال، 3n^2 + 5n + 10 ساده به O(n^2).
مثالی از Calculation
یک حلقه ی لانه دار را در نظر بگیرید که حلقه بیرونی در آن n بار اجرا می شود و حلقه ی داخلی برای هر تکرار بیرونی n * n = n^2 اجرا می شود، بنابراین بهره وری الگوریتم O(n^2) است.