در مقاله قبلی در اینباره صحبت کردیم که بهبود کارایی الگوریتم ها در برنامه نویسی، امری ضروری و مهم است و رعایت نکردن آن میتواند نرم افزار ما را کُند و یا حتی غیر قابل استفاده کند. در این مقاله میخواهیم کمی دقیق تر شویم و ببینیم که چطور میتوان سرعت الگوریتم ها را حساب کرد؟ چه معیاری نشان میدهد یک الگوریتم سریع تر از دیگری است؟ با علامت Big O آشنا میشویم و یاد میگیریم که چطور از آن برای نشان دادن سرعت الگوریتم ها استفاده کنیم و سعی میکنیم با بررسی مثال هایی، این مطلب را کاربردی تر و ساده تر کنیم.
برای محاسبه سرعت الگوریتم ها، ما فرض میگیریم که کامپیوتر، هر عملیات را در یک واحد زمانی انجام میدهد. (تفاوت سرعت انجام عملیات ها به قدری کم است که از آن صرف نظر میکنیم). پس با این فرض میتوانیم بگوییم الگوریتمی سریع تر است که تعداد عملیات کمتری انجام دهد، مهم نیست که الگوریتم شما در چند خط نوشته میشود مهم این است که تعداد عملیات هایی که کامپیوتر برای رسیدن به جواب انجام میدهید، چقدر است؟
ما از علامت O بزرگ برای نشان دادن مرتبه زمانی الگوریتم ها استفاده میکنیم. این علامت به ما نشان میدهد که الگوریتم ما به ازای هر تعداد ورودی چند عملیات انجام خواهد داد. مرتبه های زمانی بسیار زیادی وجود دارد اما در اینجا ما فقط سه مورد از آنها را به عنوان نمونه بررسی میکنیم:
مرتبه زمانی ثابت یعنی ورودی ما هرچقدر هم بزرگ یا کوچک باشد تفاوتی نمیکند در نهایت، الگوریتم ما فقط یک عملیات انجام خواهد داد، برای مثال الگوریتمِ برگرداندن آخرین عضو یک آرایه؛ تفاوتی نمیکند که این آرایه چند عضو داشته باشد در نهایت الگوریتم با انجام یک عملیات خروجی را به ما خواهد داد. نمودار پیچیدگی زمانی این الگوریتم به صورت زیر خواهد بود:
مرتبه زمانی خطی یعنی تعداد عملیات ها متناسب با تعداد ورودی ها تغییر میکند، یعنی اگر ما تعداد ورودی ها را دو برابر کنیم تعداد عملیات هم دو برابر خواهد شد، مثال برای مرتبه زمانی خطی، «جستجوی خطی در لیست» است که در مقاله قبلی درباره آن صحبت کردیم و فلوچارت آن را کشیدیم، نمودار پیچیدگی زمانی جستجوی خطی به صورت زیر خواهد بود:
مرتبه زمانی لگاریتمی به این معناست که تعداد عملیات های لازم برای الگوریتم متناسب است با لگاریتمِ تعداد ورودی ها. شاید تعریفی که گفته شد کمی ناواضح باشد. در واقع مرتبه زمانی لگاریتمی به این معناست که اگر ما تعداد ورودی ها را دو برابر کنیم، تعداد عملیات ها تنها یکی بیشتر میشود. در مقاله قبلی با الگوریتم جستجوی دودویی آشنا شدیم، این الگوریتم مثال خوبی برای پیچیدگی زمانی لگاریتمی است. نمودار پیچیدگی زمانی لگاریتمی به شکل زیر خواهد بود:
تا اینجا فهمیدیم که علامت O بزرگ برای نشان دادن پیچیدگی زمانی الگوریتم ها استفاده میشود، اما در محاسبه پیچیدگی زمانی باید به چند نکته بسیار مهم توجه داشت:
فرض کنیم ما الگوریتمی داریم که به ازای n ورودی، تعداد عملیات آن برابر با 10n خواهد بود، اگر بخواهیم پیچیدگی زمانی این الگوریتم را نشان دهید، چطور این کار را میکنید؟ شاید به ذهن تان برسد که پیچیدگی زمانی به صورت O(10n) خواهد بود اما این جواب اشتباه است به دلیل این که در محاسبه پیچیدگی زمانی ضریب ها اهمیتی ندارند و آنها را نادیده میگیریم پس پیچیدگی زمانی این الگوریتم به صورت پیچیدگی زمانی خطی یا همان O(n) خواهد بود.
در واقع ما از پیچیدگی زمانی برای نشان دادن سرعت الگوریتم ها استفاده نمیکنیم، پیچیدگی زمانی به ما نمیگوید که یک الگوریتم، در چه مدت زمانی کار را انجام میدهد، بلکه سرعت رشد زمان را در نسبت با بزرگ شدن ورودی میگوید. و دقیقا این همان چیزی است که برای ما اهمیت دارد، ما میخواهیم بدانیم که الگوریتم ما با بزرگ شدن ورودی ها چقدر کند میشود و آیا میتواند کارایی خودش را حفظ کند یا نه؟
برای محاسبه پیچیدگی زمانی ما باید حالت بدبینانه آن را در نظر بگیریم، برای مثال الگوریتم جستجوی خطی را در نظر بگیرید، ممکن است به طور اتفاقی اولین عضوی که ما بررسی میکنیم همان عضو مد نظر باشد ولی این معنا نیست که ما توانیم بگوییم پیچیدگی زمانی آن برابر با O(1) است، بلکه ما باید حالت بدبینانه را در نظر بگیریم و فرض کنیم که آخرین عضوی که بررسی میکنیم عضو مورد نظر بوده پس پیچیدگی زمانی برابر با O(n) خواهد شد
در این مقاله با مفهوم پیچیدگی زمانی آشنا شدیم و یاد گرفتیم چطور تشخیص بدهیم که یک الگوریتم، به ازای ورودی های بزرگ تر چقدر کُند میشود. با علامت O بزرگ آشنا شدیم و یاد گرفتیم که چطور به وسیله آن پیچیدگی زمانی را نشان دهیم. با مرتبه های زمانی آشنا شدیم و نمودارهایشان را دیدیم. در ادامه این دانش به ما کمک خواهد کرد که الگوریتم های کارآمد و بهینه تری بنویسیم. در مقالات بعدی از این دانش استفاده بیشتری خواهیم کرد.
خیلی ممنون از اینکه وقت گذاشتید و این مقاله رو مطالعه کردید، اگر علاقه مند هستید پیشنهاد میکنم سری مقالات الگوریتم و ساختمان داده رو مطالعه کنید. ممنون میشم نظرتون رو بهم بگید.
منبع : سری مقالات الگوریتم و ساختمان داده از سایت خودم
