بهینه‌سازی گام‌به‌گام یک الگوریتم

سفر بهینه‌سازی: یک مسئله را از O(n³) تا O(n) بهینه می‌کنیم — هر گام با تحلیل و بینش

داستان یک بهینه‌سازی

بهترین راه یادگیری بهینه‌سازی، تماشای سفر یک مسئله است. مسئله: «بیشترین جمع زیرآرایه پیوسته» (Maximum Subarray):

[-2, 1, -3, 4, -1, 2, 1, -5, 4] ← [4, -1, 2, 1] با جمع ۶

همه زیرآرایه‌ها (O(n²) جفت شروع/پایان) × جمع هر کدام O(n):

best = -∞
for i in range(n):
    for j in range(i, n):
        best = max(best, sum(arr[i:j+1]))

بینش: جمع [i..j] = prefix[j] − prefix[i−1] — جمع را O(1) کن:

for j: برای هر j، بهترین i را با min(prefix تا j−1) بگیر

یا ساده‌تر: در حلقه داخلی، جمع را «تداوم‌دار» به‌روزرسانی کن — بدون sum مجدد.

نصف کن؛ بهترین: چپ، راست، یا عبوری از وسط (از وسط به دو طرف بیشترین امتداد). T(n)=2T(n/2)+O(n).

بینش طلایی DP: best_ending_here[i] = max(arr[i], best_ending_here[i-1] + arr[i])

یعنی: یا از اینجا شروع کن، یا قبلی را ادامه بده! و جواب کلی = max همه best_ending_here.

current = best = arr[0]
for x in arr[1:]:
    current = max(x, current + x)
    best = max(best, current)

سه خط، O(n)، O(1) حافظه — زیبایی الگوریتم!

نکته: هر بهینه‌سازی از یک «بینش» می‌آید: محاسبه تکراری حذف شود / ساختار تقسیم شود / رابطه بازگشتی پیدا شود. بهینه‌سازی بدون بینش، کد قاطی است!

این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.