مهدی نوروزی
مهدی نوروزی
خواندن ۲ دقیقه·۲ سال پیش

پیچیدگی های زمانی اجرای الگوریتم با big O به زبان ساده

در تحلیل پیچیدگی های زمانی اجرای الگوریتم با نماد (N)O یا نماد هایی شبیه این مواجه شده اید ،

در واقع این نماد ها به ما میگویند که الگوریتمی که استفاده میکنیم چقدر بهینه بوده؟

سرعت اجرای آن چقدر است؟

هر برنامه نویسی باید این نماد ها را در بهترین حالت و بدترین حالت به خاطر داشته باشد مخصوصا برای استفاده از الگوریتم های مرتب سازی ، مثلا الگوریتم مرتب سازی Counting Sort در بدترین حالت (K+N)O است این نشان میدهد که بکارگیری این الگوریتم در میان کد ها از بازدهی بالایی برخوردار است ، حالا سوالی که برای اکثر خوانندگان پیش میاید این است که این (N)O و نماد های دیگر چطور بدست می آیند ؟ در اصل اصلی ترین بخش مقاله همین نکته است که چگونه این ها محاسبه میشوند و باید برای هر الگوریتم محاسبه کرد؟ خب در درس طراحی الگوریتم و یا ریاضیات گسسته این مبحث عمیقا مورد بحث و تحلیل قرار گرفته و با رجوع به آن میتوانید اطلاعات جامعی بدست آورید ، ولی در این مقاله ما به طور کوتاه و خلاصه و ابتدایی نحوه محاسبه اش را روی یک الگوریتم مرتب سازی شرح می دهیم ( عمیق شدن در این مبحث رو به خودتون واگذار میکنیم که مبحث مهمی هم است:)  )


معنای نماد ها

همچنین نماد های دیگر مثل تتا و امگا و o و w هم برای پیچیدگی زمانی الگوریتم ها استفاده میشوند ولی به طور کلی بیشتر با نماد O نمایش داده میشوند.

به طور کلی O یعنی تابع مدنظر، کوچکتر یا مساوی است.

تتا یعنی تابع مدنظر، هم رشد یا مساوی است.

امگا یعنی تابع مدنظر، بزرگتر یا مساوی است.

o یعنی تابع مدنظر، کوچکتر است.

امگا کوچک یعنی تابع مدنظر، بزرگتر است.


نحوه‌ی محاسبه‌ی (N)O

فرض کنید برای محاسبه ی پیچیدگی زمانی الگوریتم مرتب سازی حبابی ما باید مراحل زیر را انجام دهیم:

ادامه مطلب در سایت خبرکاو


https://khabarkaav.ir/%d9%be%db%8c%da%86%db%8c%d8%af%da%af%db%8c-%d9%87%d8%a7%db%8c-%d8%b2%d9%85%d8%a7%d9%86%db%8c-%d8%a7%d8%ac%d8%b1%d8%a7%db%8c-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-%d8%a8%d8%a7-big-o-%d8%a8/


الگوریتمبرنامه نویسی
مهندس نرم افزار و برنامه نویس
شاید از این پست‌ها خوشتان بیاید