خبرکاو:

نمودار رشد توابع

 

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

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

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

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

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

معنای نماد ها

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

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

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

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

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

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

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

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

محاسبه ی O

خب در این بخش ما دو حلقه تکرار داریم که هر کدام از یک تا N پیمایش میشوند به عبارت دیگر به اندازه ی N بار اجرا میشوند ، اگر هر کدام از این حلقه ها به اندازه های N بار اجرا شوند به صورت نمادی میشود (N)O که چون دو حلقه تکرار وجود دارد و هر حلقه به صورت یک واحد، افزایشی حرکت میکند و به عبارتی دیگر یعنی: یکی یکی به مقدارش اضافه میشود، سپس ما با ضرب این دو N به (N^2)O میرسیم.

نکته مهم اینکه عبارت های دیگر داخل کد چون از مرتبه (1)O است و به نوعی ثابت در ریاضی محسوب میشوند در محاسبات به آن ها اعتنا نمیشود .

این الگوریتم در بدترین حالت (N^2)O می باشد که در مقایسه با دیگر الگوریتم ها بهینه نیست . ما باید الگوریتمی انتخاب یا طراحی کنیم که در بدترین حالت چیزی در حدود (LOG N)O یا در (N+K)O باشد مثلا الگوریتم Counting Sort که در بالا نیز اشاره شد در بدترین حالت (N+K)O است و این در پیمایش حجم عظیم داده ای بهینه تر میباشد .

پیچیدگی زمانی (LOG N)O

پیچیدگی زمانی (LOG N)O یا به طور کل رنج LOG ها به الگوریتم هایی اشاره دارد که از قانون تقسیم و غلبه پیروی میکنند.

یعنی الگوریتم، برای رسیدن به نتیجه، ابتدا آرایه به دو بخش و هر کدام از آن دو بخش به دو بخش دیگر تقسیم میشوند تا به نتیجه بهینه دست پیدا کنیم ، برای مثال: در الگوریتم جستجوی باینری برای پیدا کردن یک عنصر، ابتدا مرتب میشود و بعد آرایه را به دو بخش بالایی و پایینی تقسیم میکند سپس عنصر وسط چک میشود، اگر با عنصر مورد نظر ما یکی بود که عالی، کار تمام است جستجو به پایان میرسد و بهترین حالت اتفاق افتاده است ، ولی اگر نبود با توجه به عدد مورد نظر ما مثلا عددی که ما دنبال آن هستیم 9 است ، و آرایه از 1 تا 10 مرتب شده است ،خب اینجا  10 عنصر به دو نیمه تقسیم میشوند و چون ما بدنبال عدد 9 هستیم و عدد ما در نیمه بالایی است، فقط نیمه بالایی مورد جستجو قرار میگیرد و از جستجوی نیمه پایینی صرف نظر میشود به این ترتیب ما با پیچیدگی زمانی حدود (LOG N)O به نتیجه مورد نظرمان خواهیم رسید ، این الگوریتم ها باتوجه به این مکانیزم، به (LOG N)O معروف بوده و از (N^2)O بهینه تر هستند .

نویسنده: مهدی نوروزی

منابع برای استخراج نمودار