مسئله‌ی زیر را درنظر بگیرید:

مسئله‌ی یافتن زیرآرایه با مجموع بیشینه

در علوم کامپیوتر، مسئله‌ی یافتن زیرآرایه با مجموع بیشینه، انتخاب مجموعه‌ای از خانه‌های مجاور از یک آرایه‌ی یک بعدی است که مجموع عناصر آن بیش‌ترین مقدار ممکن باشد. روش‌های مختلفی برای این مسئله می‌توان ارائه داد. به‌طور نمونه 3 الگوریتم با دیدگاه‌های مختلف در این مطلب مورد بررسی قرار خواهد گرفت تا با تحلیل هریک از آن‌ها، مفهموم مرتبه‌ی زمانی و اهمیت الگوریتم‌های کارا را نشان دهیم. برای مثال، آرایه‌ی 10 عنصری A با مقادیر زیر را درنطر بگیرید:

الگوریتم باید به‌عنوان خروجی، SUM (مقدار مجموع بیشینه)، i (اندیس شروع زیرآرایه) و j (اندیس پایان زیر آرایه) را به شرط 1 ≤ i ≤ j < n محاسبه کرده و چاپ کند. برای مثال بالا، زیر آرایه با مجموع بیشینه عبارت است از:

که دارای مجموع 20 و از اندیس 4 تا اندیس 8 قرار دارد و در شکل بالا با مربع‌های رنگی نشان داده شده است.

الگوریتم اول

برای تعیین اندیس شروع و اندیس پایان (زیرآرایه‌ی جواب)، می‌توان از دو متغیر به‌همراه حلقه‌ی تکرار استفاده کرده و هربار، ضمن محاسبه‌ی مجموع عناصر بین آن‌ها، بیشترین مقدار ممکن را نیز شناسایی کنیم. برنامه‌ی زیر به زبان C++ این دیدگاه را پیاده‌سازی کرده است:

1#include <iostream>
2using namespace std;
3void main() {
4  int A[100], n, START, END, MAXSUM = 0, SUM, I, J, K;
5  cin >> n;
6  for (I = 0; I < n; I++)
7    cin >> A[I];
8  for (I = 0; I < n; I++)
9    for (J = I; J < n; J++) {
10      SUM = 0;
11      for (K = I; K <= J; K++)
12        SUM += A[K];
13      if (SUM > MAXSUM) {
14        MAXSUM = SUM;
15        START = I;
16        END = J;
17      }
18    }
19  cout << "Maximum sum is " << MAXSUM
20    << " from " << START << " to " << END;
21}

در پیاده‌سازی این الگوریتم از 3 حلقه‌ی تکرار تودرتو استفاده شده است. طبق اصل ضرب، تعداد هر یک از حلقه‌ها در همدیگر ضرب شده و تعداد کل تکرارها به‌دست می‌آید. برای مقادیر مختلف n، تعداد کل دستورات در جدول زیر آمده است. توجه داشته باشید که برای راحتی کار، فقط تعداد اجرای پرتکرارترین دستور (خط شماره‌ی 12) شمارش شده‌است.

الگوریتم دوم

با کمی دقت در الگوریتم اول، با اندکی تغییر می‌توان حلقه‌ی سوم (داخلی‌ترین حلقه) را حذف کرد. وظیفه‌ی این حلقه، جمع تمامی اعداد محصور بین اندیس‌های I و J است. از آنجاییکه در ابتدا مقدار J برابر I است و رفته رفته از هم دور می‌شوند، لذا می‌توان همزمان با مرور مقادیر جدید توسط J، مجموع عناصر را نیز بدست آورد و نیازی به تشکیل حلقه‌ی تکرار دیگری نیست. این بهبود در کد زیر پیاده‌سازی شده و فقط با دو حلقه‌ی تکرار تودرتو نوشته شده‌است:

1#include <iostream>
2using namespace std;
3void main() {
4  int A[100], n, START = 0, END = 0, MAXSUM = 0, SUM, I, J;
5  cin >> n;
6  for (I = 0; I < n; I++)
7    cin >> A[I];
8for (I = 0; I < n; I++) {
9  SUM = 0;
10  for (J = I; J < n; J++) {
11    SUM += A[J];
12    if (SUM > MAXSUM) {
13      MAXSUM = SUM;
14      START = I;
15      END = J;
16    }
17  }
18}
19cout << "Maximum sum is " << MAXSUM
20  << " from " << START << " to " << END;
21}

برای مقادیر مختلف n، تعداد کل دستورات در جدول زیر آمده است. مانند الگوریتم قبلی، فقط تعداد اجرای پرتکرارترین دستور (خط شماره‌ی 11) شمارش شده‌است.

با مقایسه‌ی نتایج اجرای این الگوریتم (جدول بالا) با نتیجه‌ی الگوریتم اول، ملاحظه می‌شود که بهبود بسیار خوبی حاصل شده است. الگوریتم بعدی، تنها با یک حلقه‌ی تکرار نوشته شده است.

الگوریتم سوم

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

1#include <iostream>
2using namespace std;
3void main() {
4  int A[100], n, START = 0, END = 0, MAXSUM = 0, SUM = 0, I;
5  cin >> n;
6  for (I = 0; I < n; I++)
7    cin >> A[I];
8  for (I = 0; I < n; I++) {
9    if (SUM + A[I] > A[I])
10      SUM += A[I];
11    else {
12      SUM = A[I];
13      START = I;
14    }
15    if (SUM > MAXSUM) {
16      MAXSUM = SUM;
17      END = I;
18    }
19  }
20cout << "Maximum sum is " << MAXSUM
21  << " from " << START << " to " << END;
22}

برنامه‌ی بالا، برای حل مسئله فقط از یک حلقه‌ی تکرار استفاده می‌کند لذا تعداد اجرای دستورات برابر اندازه‌ی مسئله است. در جدول زیر مقایسه‌ای بین نتایج اجرای هر سه الگوریتم گفته شده در این مطلب آمده است: