بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 31: پیچیدگی زمانی و Big-O Complexity and Big-O

یاد می‌گیریم هزینه‌ی یک الگوریتم را با شمردن عملیات و نماد Big-O تخمین بزنیم و ساختار داده‌ای انتخاب کنیم که با بزرگ شدن ورودی کند نشود.

در این جلسه یاد می‌گیری

درس

Big-O نمی‌گوید برنامه چند ثانیه طول می‌کشد؛ می‌گوید با دو برابر شدن ورودی، کار چگونه رشد می‌کند. ضرایب ثابت و جمله‌های کوچک‌تر حذف می‌شوند: 3n + 5 همان O(n) است. ساده‌ترین راه حس کردن آن، شمردن عملیات است.

def count_linear(n):
    ops = 0
    for _ in range(n):
        ops += 1
    return ops

print(count_linear(10), count_linear(20))

دو حلقه‌ی تودرتو روی همان ورودی معمولاً O(n²) است: با دو برابر شدن n، کار چهار برابر می‌شود. برای n = 100_000 این یعنی حدود ده میلیارد عمل؛ عملاً غیرقابل‌اجرا.

def count_pairs(n):
    ops = 0
    for i in range(n):
        for j in range(i + 1, n):
            ops += 1
    return ops

print(count_pairs(10), count_pairs(20))

O(log n) یعنی در هر گام مسئله نصف می‌شود؛ برای یک میلیون عنصر حدود ۲۰ گام. جدول ذهنی برای n = 1000: O(1) ≈ ۱، O(log n) ≈ ۱۰، O(n) = ۱۰۰۰، O(n log n) ≈ ۱۰٬۰۰۰، O(n²) = یک میلیون.

n, steps = 1000, 0
while n > 1:
    n //= 2
    steps += 1
print(steps)

x in some_list کل لیست را پیمایش می‌کند (O(n)) اما x in some_set با hash مستقیم به خانه‌ی درست می‌رود (میانگین O(1)). اگر داخل یک حلقه عضویت می‌پرسید، ساختن یک set می‌تواند O(n²) را به O(n) تبدیل کند.

allowed = ["read", "write", "admin"]
allowed_set = set(allowed)
requests = ["read", "delete", "admin"]
print([r for r in requests if r in allowed_set])

هزینه‌ی عملیات رایج لیست: append و pop() از انتها O(1) (سرشکن یا amortized)؛ insert(0, x) و pop(0) و remove و index از مرتبه‌ی O(n) هستند چون باید عناصر را جابه‌جا یا پیمایش کنند. dict و set در خواندن، نوشتن و حذف میانگین O(1) دارند.

پیش‌محاسبه هم یک ابزار است: با یک آرایه‌ی پیشوند جمع (prefix sum) در O(n)، هر پرس‌وجوی «جمع بازه» در O(1) جواب داده می‌شود. این همان معامله‌ی کلاسیک حافظه در برابر زمان است.

nums = [3, 1, 4, 1, 5]
prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
print(prefix[4] - prefix[1])

مثال‌های این جلسه

چالش‌ها

  1. Counting Comparisons (آسان)
  2. Counting Pairs (آسان)
  3. Banned Words (آسان)
  4. Duplicate Detection (متوسط)
  5. Growth Table (متوسط)
  6. Range Sum Queries (متوسط)
  7. Join with a Dict (متوسط)
  8. First Repeat (سخت)
  9. Sliding Window (سخت)
  10. Measuring Growth (سخت)
  11. Anagram by Counting (متوسط)
  12. Two Pointers (سخت)

بیشتر بخوان

← جلسه‌ی 30: پروژه: سامانه‌ی کتابخانه جلسه‌ی 32: جست‌وجو →