جلسهی 31: پیچیدگی زمانی و Big-O Complexity and Big-O
یاد میگیریم هزینهی یک الگوریتم را با شمردن عملیات و نماد Big-O تخمین بزنیم و ساختار دادهای انتخاب کنیم که با بزرگ شدن ورودی کند نشود.
در این جلسه یاد میگیری
- رشد زمان اجرا را با نماد
Big-Oتوصیف کنید:O(1)،O(log n)،O(n)،O(n log n)،O(n²). - با یک شمارندهی واقعی تعداد عملیات دو الگوریتم را اندازه بگیرید و مقایسه کنید.
- بدانید عضویت (
in) درlistاز مرتبهیO(n)و درset/dictبهطور میانگینO(1)است. - الگوهای خطی مثل پیشوند جمع (
prefix sum) و پنجرهی لغزان را جایگزین حلقههای تودرتو کنید.
درس
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])مثالهای این جلسه
- مثال تابع در پایتون: def count_linear(n):
- مثال تابع در پایتون: def count_pairs(n):
- مثال حلقه while در پایتون: while n > 1: — پیچیدگی زمانی و Big-O
- مثال list comprehension در پایتون: print([r for r in requests if r in allowed_…
- مثال حلقه for در پایتون: for x in nums:
چالشها
- Counting Comparisons (آسان)
- Counting Pairs (آسان)
- Banned Words (آسان)
- Duplicate Detection (متوسط)
- Growth Table (متوسط)
- Range Sum Queries (متوسط)
- Join with a Dict (متوسط)
- First Repeat (سخت)
- Sliding Window (سخت)
- Measuring Growth (سخت)
- Anagram by Counting (متوسط)
- Two Pointers (سخت)