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

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

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

در اینجا چند نمونه از پیچیدگی‌های زمانی و الگوریتم‌های مربوط به آن‌ها آورده شده است:

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

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

int getFirstElement(int arr[]) {
  return arr[0];
}

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

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

یک الگوریتم با پیچیدگی زمانی خطی، با افزایش اندازه ورودی آن، زمان متناسبی برای اجرا خواهد داشت. به‌عنوان‌مثال، اگر یک الگوریتم برای پردازش 10 عنصر 1 ثانیه طول بکشد، پردازش 100 عنصر تقریباً 10 ثانیه طول می‌کشد. در اینجا مثالی از یک تابع C++ با پیچیدگی زمانی خطی آورده شده است:

int findElement(int arr[], int n, int x) {
  for(int i=0; i<n; i++) {
    if(arr[i] == x) {
      return i;
    }
  }
  return -1;
}

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

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

یک الگوریتم با پیچیدگی زمانی درجه دوم، با افزایش اندازه ورودی آن، زمان بسیار بیشتری برای اجرا نیاز دارد. به‌عنوان‌مثال، اگر یک الگوریتم برای پردازش 10 عنصر 1 ثانیه طول بکشد، پردازش 100 عنصر تقریباً 100 ثانیه طول می‌کشد. در اینجا یک مثال از یک تابع ++C با پیچیدگی زمانی درجه دوم آورده شده است:

void printPairs(int arr[], int n) {
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      cout << arr[i] << &quot,&quot << arr[j] << endl;
    }
  }
}

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

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