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

کارایی یک الگوریتم به مقدار زمان، حافظهحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوتردر این مقاله به بررسی کامل حافظه در کامپیوتر، انواع حافظه در کامپیوتر، کش، روش‌های آدرس دهی کش، نگاشت آدرس و موارد دیگر می‌پردازیم و سایر منابع مورد نیاز برای اجرا بستگی دارد. کارایی یک الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد با بررسی پیچیدگی و مرتبه زمانی و حافظه‌ای و کمک نمادهای مجانبی اندازه‌گیری می‌شود. یک الگوریتم ممکن است عملکرد یکسانی برای انواع مختلف ورودی نداشته باشد و با افزایش اندازه ورودی، عملکردش تغییر کند. مطالعه تغییر در عملکرد الگوریتم با تغییر در ترتیب اندازه ورودی به‌عنوان تحلیل مجانبی تعریف می‌شود. در این مقاله با بررسی این مفاهیم و تعریف‌شان یاد خواهیم گرفت که چگونه کارایی یک الگوریتم را از نظر مرتبه زمانی توصیف کنیم.

نمادهای مجانبی

نمادهای مجانبی، نمادهای ریاضی هستند که برای توصیف زمان اجرای یک الگوریتم در زمانی که ورودی به سمت یک مقدار خاص یا یک مقدار محدود میل می‌کند، استفاده می‌شود؛ به‌عنوان مثال در مرتب سازی حبابیآموزش مرتب سازی حبابی (Bubble Sort) بصورت 0 تا 100این صفحه مرتب سازی حبابی (Bubble Sort) را بصورت 0 تا 100 آموزش داده و کدهای مرتب سازی حبابی در C++، پایتون و جاوا آورده شده است شده، زمانی که آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه ورودی از قبل مرتب شده است، زمان صرف شده توسط الگوریتم خطی است، یعنی بهترین حالت؛ اما زمانی که آرایه ورودی در شرایط معکوس قرار دارد، الگوریتم حداکثر زمان را برای مرتب‌سازی عناصر یعنی بدترین حالت صرف می‌کند. وقتی آرایه ورودی نه مرتب شده است و نه به ترتیب معکوس، آن‌گاه به زمان متوسطی نیاز دارد. این مدت زمان‌ها با استفاده از نمادهای مجانبی نشان داده می‌شوند.

عمدتاً سه نماد مجانبی وجود دارد:

• نماد Big-O
• نماد امگا
• نماد تتا

در ادامه هریک از این نمادها را تعریف و بررسی می‌کنیم.

نماد Big-O یا (O)

نماد Big-O حد بالایی زمان اجرای یک الگوریتم، یعنی بدترین حالت اجرای الگوریتم را نشان می‌دهد. این نماد به صورت زیر تعریف می‌شود:

$\mathrm{O}\left(\mathrm{g}\left(\mathrm{n}\right)\right)\mathrm{=f}\left(\mathrm{n}\right)$ ثابت‌های مثبت $\mathrm{c}$ و ${\mathrm{n}}_0$ وجود دارد به طوری که $\mathrm{f}\left(\mathrm{n}\right)\mathrm{\le }\mathrm{cg}\left(\mathrm{n}\right)\mathrm{\le }\mathrm{0}$ برای همه $\mathrm{n}\mathrm{\ge }{\mathrm{n}}_0$

اگر یک ثابت مثبت c وجود داشته باشد که برای nهای به اندازه کافی بزرگ، بین 0 و cg(n) باشد، عبارت فوق را می توان به‌صورت روبرو توصیف کرد: تابع f(n) از مرتبه O(g(n)) است. یعنی برای هر مقدار n، زمان اجرای یک الگوریتم از زمان ارائه شده توسط O(g(n)) بیشتر نمی‌شود. از آن جایی که نماد Big-O بدترین زمان اجرای یک الگوریتم را ارائه می‌دهد، به‌طور گسترده‌ای برای تجزیه و تحلیل یک الگوریتم استفاده می شود، زیرا ما همیشه به بدترین حالت اجرای الگوریتم اهمیت می‌دهیم.

نماد امگا (Ω)

نماد امگا نشان دهنده مرز پایینی زمان اجرای یک الگوریتم است بنابراین، بهترین حالت پیچیدگی یک الگوریتم را مشخص می‌کند. این نماد به صورت زیر تعریف می‌شود:

$\mathrm{\Omega }\left(\mathrm{g}\left(\mathrm{n}\right)\right)\mathrm{=f}\left(\mathrm{n}\right)$ ثابت‌های مثبت $\mathrm{c}$ و ${\mathrm{n}}_0$ وجود دارد به طوری که $\mathrm{cg}\left(\mathrm{n}\right)\mathrm{\le }\mathrm{f}\left(\mathrm{n}\right)\mathrm{\le }\mathrm{0}$ برای همه $\mathrm{n}\mathrm{\ge }{\mathrm{n}}_0$

عبارت فوق را می‌توان به عنوان تابع f(n) از مرتبه Ω(g(n)) توصیف کرد، اگر یک ثابت مثبت c وجود داشته باشد به طوری که برای n به اندازه کافی بزرگ، f(n) بالای cg(n) باشد. برای هر مقدار n، حداقل زمان مورد نیاز الگوریتم توسط امگا Ω(g(n)) داده می شود.

نماد تتا (Θ)

نماد تتا تابع را از بالا و پایین محصور می‌کند. از آن‌جایی که این نماد کران بالایی و پایینی زمان اجرای یک الگوریتم را نشان می‌دهد، برای تجزیه و تحلیل پیچیدگی میانگین حالت یک الگوریتم استفاده می‌شود.

برای تابع g(n) ،Θ(g(n)) با رابطه به‌دست می‌آید:

$\mathrm{\theta }\left(\mathrm{g}\left(\mathrm{n}\right)\right)\mathrm{=f}\left(\mathrm{n}\right)$ ثابت‌های مثبت ${\mathrm{n}}_0$، ${\mathrm{c}}_1$ و ${\mathrm{c}}_2$ وجود دارد به طوری که ${\mathrm{c}}_{\mathrm{1}}\mathrm{gn}\mathrm{\le }\mathrm{f}\left(\mathrm{n}\right)\mathrm{\le }{\mathrm{c}}_{\mathrm{2}}\mathrm{gn}\mathrm{\le }\mathrm{0}$ برای همه $\mathrm{n}\mathrm{\ge }{\mathrm{n}}_0$

یعنی اگر ثابت‌های مثبت c1 و c2 وجود داشته باشد، به طوری که برای n‌های به اندازه کافی بزرگ بتوان f(n) را بین c₁g(n) و c₂g(n) قرار داد، می‌توان آن را به‌عنوان تابع f(n) از مرتبه Θ(g(n)) توصیف کرد. اگر تابع f(n) در جایی بین c₁g(n) و c₂g(n) برای همه n ≥ n0 قرار گیرد، آنگاه به f(n) مجانبی کران دار گفته می‌شود.

پیچیدگی زمانی های مهم

یکی از عوامل اساسی که بر عملکرد و کارایی برنامه شما تأثیر می‌گذارد، سخت افزارسخت افزار چیست - بررسی اجزای اصلی سخت افزار کامپیوتردر این صفحه بررسی شده که سخت افزار چیست و سخت افزار کامپیوتر به زبان ساده معرفی شده است، همچنین به بررسی اجزای اصلی سخت افزار کامپیوتر پرداخته شده است، سیستم عاملسیستم عامل چیست به زبان ساده، چرا باید از OS استفاده کنیم؟این مقاله عالی به معرفی سیستم عامل (Operating System|OS) به زبان ساده پرداخته، همچنین بررسی کرده که چرا باید از سیستم عامل استفاده کنیم و پردازنده (CPU)پردازنده (CPU) چیست؟ بررسی انواع، وظایف و کاربردهاسی پی یو قلب کامپیوتر و کامپیوتر قلب دنیای کنونی است، بنابراین در این صفحه به معرفی و بررسی سی‌پی‌یو یا همان پردازنده مرکزی (CPU) پرداخته‌ شده، و بطور کامل توضیح داده‌ایم که CPU از چه بخش هایی تشکیل شده و هر بخش چه وظایف و مشخصاتی دارد. است که استفاده می‌کنید، اما وقتی عملکرد یک الگوریتم را تجزیه و تحلیل می‌کنید، این را در نظر نمی‌گیرید. در عوض، پیچیدگی زمان و مکان به‌عنوان تابعی از اندازه ورودی مهم است. پیچیدگی زمانی یک الگوریتم مشخص می‌کند که چقدر طول می‌کشد تا یک الگوریتم بر اساس تابعی از اندازه ورودی آن اجرا شود. در این قسمت ما با مثال، چند مورد از پیچیدگی های زمانی مهم را با مثال بررسی می‌کنیم:

پیچیدگی زمانی ثابت O(1)

زمانی که الگوریتم به اندازه ورودی n وابسته نباشد، گفته می شود که پیچیدگی زمانی ثابت با مرتبه O(1) دارد. صرف نظر از اندازه ورودی n، زمان اجرا همیشه یکسان خواهد بود. مثال زیر را در نظر بگیرید:

#include <iostream>
using namespace std;

int main()
{
  cout << "Hello World";
  return 0;
}

#include <iostream>
using namespace std;

int main()
{
  cout << "Hello World";
  return 0;
}

کپی کردن کد

در کد بالا "Hello World" فقط یک بار روی صفحه چاپ می‌شود بنابراین، پیچیدگی زمانی ثابت است: O(1) یعنی هربار مقدار ثابتی از زمان برای اجرای کد مورد نیاز است، بدون توجه به این که از کدام سیستم‌عامل یا چه سخت‌افزاری استفاده می‌کنید.

پیچیدگی زمانی خطی O(n)

زمانی گفته می‌شود که یک الگوریتم دارای پیچیدگی زمانی خطی است که زمان اجرا به‌صورت خطی با اندازه ورودی افزایش می‌یابد. هنگامی که تابع شامل بررسی تمام مقادیر در داده‌های ورودی با تعداد دفعات ثابت است، پیچیدگی زمانی‌اش از مرتبه O(n) است. مثال زیر را در نظر بگیرید:

#include <iostream>
using namespace std;
 
int main()
{
  int i, n = 8;
  for (i = 1; i = n; i++) {
    cout << "Hello World \n";
  }
  return 0;
}

#include <iostream>
using namespace std;
 
int main()
{
  int i, n = 8;
  for (i = 1; i = n; i++) {
    cout << "Hello World \n";
  }
  return 0;
}

کپی کردن کد

در کد بالا "Hello World" فقط n بار روی صفحه چاپ می‌شود، زیرا مقدار n می‌تواند تغییر کند بنابراین پیچیدگی زمانی خطی است: O(n) یعنی هربار، مقدار خطی زمان برای اجرای کد مورد نیاز است.

پیچیدگی زمانی لگاریتمی O(Log n)

زمانی گفته می‌شود که یک الگوریتم دارای پیچیدگی زمانی لگاریتمی است که اندازه داده‌های ورودی را در هر مرحله کاهش دهد. این نشان می‌دهد که تعداد عملیات با اندازه ورودی یکسان نیست. با افزایش اندازه ورودی، تعداد عملیات کاهش می‌یابد. الگوریتم‌های با پیچیدگی لگاریتمی در درخت‌های باینری یا توابع جستجوی باینری یافت می‌شوند. این الگوریتم‌ها شامل جستجوی یک مقدار معین در یک آرایه با تقسیم آرایه به دو بخش و شروع به جستجو در یک قسمت است. این روش تضمین می‌کند که عملیات روی هر عنصر داده انجام نمی‌شود. مثال زیر را در نظر بگیرید:

#include <iostream>
using namespace std;
 
int main()
{
  int i, n = 8;
  for (i = 1; i = n; i=i*2) {
    cout << "Hello World \n";
  }
  return 0;
}

#include <iostream>
using namespace std;
 
int main()
{
  int i, n = 8;
  for (i = 1; i = n; i=i*2) {
    cout << "Hello World \n";
  }
  return 0;
}

کپی کردن کد

در الگوریتم بالا، تعداد چاپ "Hello World" با اندازه ورودی نسبت خطی ندارد چون در هر مرحله i بجای یک واحد افزایش، دوبرابر می‌شود، این یعنی تعداد دفعات چاپ "Hello World" برابر با Log n بار است پس این الگوریتم از مرتبه لگاریتمی O(Log n) است.

پیچیدگی زمانی درجه دوم O(n²)

گفته می‌شود که یک الگوریتم دارای پیچیدگی زمانی درجه دو است، اگر در آن، زمان اجرا به صورت غیرخطی (n²) با طول ورودی افزایش یابد. به‌طور کلی، حلقه‌های تودرتویی در این دسته قرار می‌گیرند که در آنها یک حلقهحلقه در برنامه نویسی چیست؟ حلقه یا لوپ (Loop) چیست؟این مقاله عالی به زبان ساده و با استفاده از فیلم توضیح داده که حلقه در برنامه نویسی چیست، همچنین در خصوص حلقه یا لوپ (Loop) بی نهایت صحبت کرده است از مرتبه O(n) درون یک حلقه دیگر از همین مرتبه قرار داشته باشد. آن‌گاه پیچیدگی زمانی آنها از مرتبه O(n)*O(n) = O(n²) خواهد شد. به‌طور مشابه، اگر m حلقه تودرتو با مرتبه زمانی O(n)‌ در تابع تعریف شده باشند، پیچیدگی زمانی از مرتبه O(nm) خواهد شد که به آنها توابع با پیچیدگی زمانی چند جمله ای می‌گویند. مثال زیر را در نظر بگیرید:

#include <iostream>
using namespace std;
 
int main()
{
  int i, n = 8;
  for (i = 1; i = n; i=i+1) {
    for (i = 1; i = n; i=i+1) {
      cout << "Hello World \n";
    }
  }
  return 0;
}

#include <iostream>
using namespace std;
 
int main()
{
  int i, n = 8;
  for (i = 1; i = n; i=i+1) {
    for (i = 1; i = n; i=i+1) {
      cout << "Hello World \n";
    }
  }
  return 0;
}

کپی کردن کد

در این مثال دو حلقه تودرتو داریم که هرکدام n بار اجرا می‌شوند. یعنی هرکدام از مرتبه O(n) هستند. با اجرای این حلقه، عبارت "Hello World" به اندازه n² بار اجرا می‌شود پس پیچیدگی زمانی این الگوریتم از مرتبه O(n²) است.

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

• مرتب‌سازی درجی: پیچیدگی زمانی Insertion Sort یا مرتب سازی درجیآموزش الگوریتم مرتب سازی درجی (Insertion Sort) 0 تا 100در این صفحه مرتب سازی درجی (Insertion Sort) به بهترین روش ممکن آموزش داده شده و روش‌های محتلف پیاده‌سازی الگوریتم مرتب سازی درجی بیان شده است. در بهترین حالت O(n) و در بدترین حالت، پیچیدگی زمانی O(n²) است.
• مرتب سازی ادغامی: پیچیدگی زمانی مرتب سازی ادغامیآموزش مرتب سازی ادغامی بصورت 0 تا 100این صفحه مرتب سازی ادغامی را بصورت 0 تا 100 آموزش داده و مثال مرتب سازی ادغامی آورده شده است، همچنین بهترین، متوسط و بدترین حالت مرتب سازی ادغامی بررسی شده یا Merge Sort در بهترین حالت O(n Log n) و در بدترین حالت، پیچیدگی زمانی O(n Log n) است؛ به این دلیل که Merge Sort تعداد یکسانی از مراحل مرتب‌سازی را در همه حالات اجرا می‌کند.
• مرتب سازی حبابی: پیچیدگی زمانی Bubble Sort یا مرتب سازی حبابیآموزش الگوریتم مرتب سازی حبابی (Bubble Sort) از 0 تا 100این صفحه مرتب سازی حبابی (Bubble Sort) را بصورت 0 تا 100 آموزش داده و کدهای مرتب سازی حبابی در C++، پایتون و جاوا آورده شده است شده در بهترین حالت O(n) و در بدترین حالت، پیچیدگی زمانی O(n²) است.
• مرتب سازی سریع: مرتب سازی سریعآموزش مرتب سازی سریع بصورت 0 تا 100این صفحه مرتب سازی سریع را بصورت 0 تا 100 آموزش داده و مثال مرتب سازی سریع آورده شده است، همچنین بهترین، متوسط و بدترین حالت مرتب سازی سریع بررسی شده یا Quick Sort در بهترین حالت O(n Log n) و در بدترین حالت، پیچیدگی زمانی O(n²) است. Quick Sort به‌دلیل عملکرد O(n Log n) در بهترین و متوسط، سریع‌ترین الگوریتم مرتب‌سازی در نظر گرفته می‌شود.

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

• جستجوی خطی: جستجوی خطی از اول و به ترتیب لیست یا آرایه را جستجو می‌کند. پیچیدگی زمانی جستجوی خطی در بهترین حالت O(1) و در بدترین حالت، پیچیدگی زمانی O(n) است.
• جستجوی باینری: جستجوی باینری سریع‌تر از الگوریتم جستجوی خطی است، با این حال برای آرایه‌های کوچکتر، جستجوی خطی عملکرد بهتری دارد. پیچیدگی زمانی جستجوی باینری در بهترین حالت O(1) و در بدترین حالت، پیچیدگی زمانی O(Log n) است.

جمع‌بندی

در این مقاله، متوجه شدیم که پیچیدگی زمانی چیست، عملکرد یک الگوریتم چگونه با استفاده از نماد O بزرگ تعیین می‌شود و پیچیدگی‌های زمانی مختلفی را با مثال‌ بررسی کردیم؛ همچنین پیچیدگی زمانی برخی الگوریتم‌های مهم مرتب‌سازی و جستجو را هم بررسی کردیم.

مطالب مرتبط

همه مقالات

معرفی انواع عملگرها در برنامه نویسی⚡️منطقی، محاسباتی و بیتی

توضیح تابع بازگشتی، دنباله بازگشتی و رابطه بازگشتی

ماتریس در ساختمان داده⚡️معرفی انواع ماتریس (خلوت،قطری)

قضیه اصلی (Master) در ساختمان داده و طراحی الگوریتم