کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

این صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده

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

نمودار پیچیدگی زمانی

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

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

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

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

نماد 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) را بین c1g(n) و c2g(n) قرار داد، می‌توان آن را به‌عنوان تابع f(n) از مرتبه Θ(g(n)) توصیف کرد. اگر تابع f(n) در جایی بین c1g(n) و c2g(n) برای همه n ≥ n0 قرار گیرد، آنگاه به f(n) مجانبی کران دار گفته می‌شود.

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

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

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

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

#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;
}

در کد بالا "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;
}

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

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

گفته می‌شود که یک الگوریتم دارای پیچیدگی زمانی درجه دو است، اگر در آن، زمان اجرا به صورت غیرخطی (n2) با طول ورودی افزایش یابد. به‌طور کلی، حلقه‌های تودرتویی در این دسته قرار می‌گیرند که در آنها یک حلقهحلقه در برنامه نویسی چیست؟ حلقه یا لوپ (Loop) چیست؟حلقه در برنامه نویسی چیست؟ حلقه یا لوپ (Loop) چیست؟این مقاله عالی به زبان ساده و با استفاده از فیلم توضیح داده که حلقه در برنامه نویسی چیست، همچنین در خصوص حلقه یا لوپ (Loop) بی نهایت صحبت کرده است از مرتبه O(n) درون یک حلقه دیگر از همین مرتبه قرار داشته باشد. آن‌گاه پیچیدگی زمانی آنها از مرتبه O(n)*O(n) = O(n2) خواهد شد. به‌طور مشابه، اگر 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;
}

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

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

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

جمع‌بندی

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

پیچیدگی زمانی چیست؟

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

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

O(1) کمترین پیچیدگی را دارد و اغلب به آن "زمان ثابت" می‌گویند، اگر بتوانید الگوریتمی برای حل مسئله در O(1) ایجاد کنید، احتمالاً بهترین الگوریتم را ایجاد کرده‌اید.

مهم ترین پیچیدگی های زمانی کدام اند؟

پیچیدگی زمان ثابت یا O(1) - پیچیدگی زمانی لگاریتمی یا O(Log n) - پیچیدگی زمانی خطی یا O(n) - پیچیدگی زمانی O(n Log n) - پیچیدگی زمانی درجه دوم یا O(n2)

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (4 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200