# فصل ۰۷ — `Big-O`: یک پیش‌بینی، نه یک برچسب

<div dir="rtl">

# فصل ۰۷ — `Big-O`: یک پیش‌بینی، نه یک برچسب

## در این فصل چه یاد می‌گیری

تابعی داریم که کارش `3n² + 100n + 5000` عمل است. **در `n = 10` سهمِ جملهٔ `n²` از کلِ کار `4.8` درصد است. در `n = 10,000` می‌شود `99.7` درصد.**

آن دو عدد کلِ دلیلِ وجودِ `Big-O` را می‌سازند: **در `n`های بزرگ فقط یک جمله می‌ماند و بقیه گم می‌شوند.** پس اگر بخواهی رفتارِ `n`های بزرگ را در یک عبارتِ کوتاه بگویی، فقط همان جمله را می‌نویسی — و اسمش می‌شود `O(n²)`.

بعد سراغِ چیزی می‌رویم که `Big-O` **عمداً** نمی‌گوید. دو تابع می‌سازیم که هر دو `O(n)` هستند و **یکی‌شان دقیقاً سه برابرِ دیگری کار می‌کند**؛ و یک تابع را روی دو ورودیِ متفاوت می‌بریم که یکی `1` مقایسه لازم دارد و دیگری `499,500` تا.

![یک ذره‌بین بزرگ روی یک عبارتِ سه‌جمله‌ای که فقط جملهٔ اول را پررنگ نگه داشته](/lesson-assets/t1-s07-big-o/prompt/01-image-magnifier-dominant-term.png)

آخر این فصل می‌توانی:

- `Big-O` را در یک جمله تعریف کنی و بگویی دربارهٔ کدام بازهٔ `n` حرف می‌زند
- جملهٔ غالب را پیدا کنی و بقیه را حذف کنی، با دلیلِ عددی
- بگویی چرا ثابت‌ها حذف می‌شوند و چرا این **حذفِ اطلاعات** است، نه بی‌اهمیت بودنشان
- سه چیزی را که `Big-O` نمی‌گوید نام ببری

## قبل از شروع

**از فصلِ ۶:** شش مرتبهٔ رشد و نمادِ `O(...)`. **از فصلِ ۵:** ستونِ نسبت. **از فصلِ ۴:** شمارندهٔ عملیات.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-1-measure-then-predict/session-07-big-o.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. تعریفِ کاری

> **`O(f(n))` یعنی: وقتی `n` به‌اندازهٔ کافی بزرگ شود، کارِ این کد از یک ضریبِ ثابت ضربدرِ `f(n)` بیشتر نمی‌شود.**

سه کلمه در این جمله وزن دارند:

- **«وقتی `n` به‌اندازهٔ کافی بزرگ شود»** — `Big-O` دربارهٔ `n`های کوچک هیچ ادعایی نمی‌کند. این را در بخشِ ۳ با عدد می‌بینی و فصلِ ۹ کلاً دربارهٔ همان است.
- **«یک ضریبِ ثابت»** — عددی که به `n` بستگی ندارد. سه برابر، صد برابر، هزار برابر؛ `Big-O` هیچ‌کدام را نمی‌بیند.
- **«بیشتر نمی‌شود»** — `Big-O` یک **سقف** است، نه یک اندازه‌گیریِ دقیق.

**و مهم‌ترین نکته که در عنوانِ فصل هم هست: این یک پیش‌بینی است.** «این کد `O(n²)` است» یعنی «اگر `n` را دو برابر کنی، انتظار داشته باش کار حدودِ چهار برابر شود». **و هر پیش‌بینی‌ای آزمون‌پذیر است** — فصلِ بعد کارِ آزمونش را انجام می‌دهد.

> 🌱 **ریشه‌اش کجاست:** `f(n)` در این نماد دقیقاً همان **تابع** است: ماشینی که `n` می‌گیرد و یک عدد بیرون می‌دهد. اگر این تصویر برایت تازه است، [ریشه ترمِ ۴ فصل ۱](/courses/risheh/lessons/term-4-functions/session-01-function-machine) از صفر می‌سازدش — و بعدش `O(n²)` فقط یک نامِ کوتاه برای «آن ماشینی که خروجی‌اش با مربعِ ورودی می‌رود» است.

## ۲. جملهٔ غالب

تابعی را در نظر بگیر که سه بخشِ کار دارد: یک حلقهٔ تودرتو، یک حلقهٔ ساده، و یک آماده‌سازیِ ثابت.

> 🤔 **اول حدس بزن:** در `n = 10`، فکر می‌کنی سهمِ حلقهٔ تودرتو از کلِ کار چند درصد است؟ بیشتر از نصف یا کمتر؟ و در `n = 10,000` چطور؟

</div>

```python
def work(n):
    """سه بخشِ کارِ یک تابعِ فرضی: یک حلقهٔ تودرتو، یک حلقهٔ ساده، یک آماده‌سازی."""
    return 3 * n * n, 100 * n, 5_000


print(f"{'n':>8}{'3n²':>14}{'100n':>12}{'5000':>10}{'جمع':>16}{'سهمِ 3n²':>12}")
for n in (10, 100, 1_000, 10_000):
    square, linear, setup = work(n)
    total = square + linear + setup
    print(f"{n:>8,}{square:>14,}{linear:>12,}{setup:>10,}{total:>16,}"
          f"{100 * square / total:>11.1f}%")
```

```text
       n           3n²        100n      5000             جمع    سهمِ 3n²
      10           300       1,000     5,000           6,300        4.8%
     100        30,000      10,000     5,000          45,000       66.7%
   1,000     3,000,000     100,000     5,000       3,105,000       96.6%
  10,000   300,000,000   1,000,000     5,000     301,005,000       99.7%
```

<div dir="rtl">

**در `n = 10` جملهٔ `n²` کوچک‌ترین بخشِ کار است — کمتر از پنج درصد. در `n = 10,000` تقریباً تمامِ کار است.**

این همان چیزی است که «جملهٔ غالب» یعنی. **جمله‌ای که با بزرگ شدنِ `n` سریع‌تر از بقیه رشد می‌کند، دیر یا زود همه‌شان را می‌بلعد** — و از آن نقطه به بعد، نوشتنِ `+ 100n + 5000` هیچ اطلاعاتِ مفیدی اضافه نمی‌کند.

پس می‌نویسیم `O(n²)` و تمام. **دو کار انجام دادیم: جمله‌های کوچک‌تر را انداختیم، و ضریبِ `3` را هم انداختیم.** دومی موضوعِ بخشِ ۴ است.

## ۳. همان تابع، دو بازه

اگر جملهٔ غالب فقط در `n`های بزرگ غالب است، پس در `n`های کوچک جدولِ ما چه شکلی است؟

</div>

```python
for label, ladder in (("اندازه‌های کوچک", (10, 20, 40, 80)),
                      ("اندازه‌های بزرگ", (1_000, 2_000, 4_000, 8_000))):
    print(f"— {label}")
    table([(n, sum(work(n))) for n in ladder], "کارِ کل", ",d")
    print()
```

```text
— اندازه‌های کوچک
         n           کارِ کل     نسبت به سطر قبل
        10             6,300                   —
        20             8,200                1.30
        40            13,800                1.68
        80            32,200                2.33

— اندازه‌های بزرگ
         n           کارِ کل     نسبت به سطر قبل
     1,000         3,105,000                   —
     2,000        12,205,000                3.93
     4,000        48,405,000                3.97
     8,000       192,805,000                3.98
```

<div dir="rtl">

**`1.30`، `1.68`، `2.33` در برابرِ `3.93`، `3.97`، `3.98`.**

جدولِ اول اصلاً شبیهِ `O(n²)` نیست و **دروغ هم نمی‌گوید**: در آن بازه، کارِ این تابع واقعاً با مربعِ `n` نمی‌رود، چون آن `5000`ِ ثابت هنوز غالب است. **`Big-O` در آن ناحیه ادعایی ندارد و اگر کسی از آن جدول نتیجهٔ `Big-O` بگیرد، خودش را گول زده.**

> ✅ **چک کن:** ستونِ نسبتِ جدولِ دوم به‌سمتِ `4` می‌رود ولی هرگز دقیقاً `4` نمی‌شود. اگر ادامه‌اش بدهی — `16,000` و `32,000` — باید `3.99` و بعد `4.00` ببینی. **اگر برعکس دیدی که از `4` رد شد و با بزرگ شدنِ `n` بالاتر رفت، فرمول را جایی اشتباه تایپ کرده‌ای؛ نسبتِ هر تابعی با جملهٔ غالبِ `n²` با بزرگ شدنِ `n` به `4` نزدیک می‌شود، از بالا یا از پایین، و از آن دور نمی‌شود.**

## ۴. چرا ثابت‌ها حذف می‌شوند

دو تابع می‌نویسیم که هر دو یک بار روی همهٔ داده می‌روند — یکی با یک عبور، دیگری با سه.

</div>

```python
def one_pass(values):
    ops = 0
    for _ in values:
        ops += 1
    return ops


def three_passes(values):
    ops = 0
    for _ in values:
        ops += 1
    for _ in values:
        ops += 1
    for _ in values:
        ops += 1
    return ops


LADDER = [1_000, 2_000, 4_000, 8_000]
data = {n: list(range(n)) for n in LADDER}
print(f"{'n':>10}{'one_pass':>12}{'three_passes':>15}{'نسبتِ دو نسخه':>16}")
for n in LADDER:
    a, b = one_pass(data[n]), three_passes(data[n])
    print(f"{n:>10,}{a:>12,}{b:>15,}{b / a:>15.2f}")
```

```text
         n    one_pass   three_passes   نسبتِ دو نسخه
     1,000       1,000          3,000           3.00
     2,000       2,000          6,000           3.00
     4,000       4,000         12,000           3.00
     8,000       8,000         24,000           3.00
```

<div dir="rtl">

**هر دو `O(n)` هستند و یکی‌شان دقیقاً سه برابرِ دیگری کار می‌کند. هر دو جمله درست‌اند.**

دلیلِ حذفِ ثابت این نیست که ضریبِ `3` بی‌اهمیت است؛ دلیلش این است که **`Big-O` به سؤالِ دیگری جواب می‌دهد**: «اگر داده‌ام ده برابر شود، چه بلایی سرم می‌آید؟» و جوابِ آن سؤال برای هر دو یکی است — ده برابر. **ضریبِ `3` جوابِ سؤالِ «الان چقدر طول می‌کشد» است، و آن سؤالِ ساعت است، نه سؤالِ `Big-O`.**

و ضریب واقعاً هست، نه فقط روی کاغذ:

</div>

```python
fast = clock(lambda: one_pass(data[8_000]), repeat=3)
slow = clock(lambda: three_passes(data[8_000]), repeat=3)
print(f"one_pass     : {1000 * fast:>7.2f} ms")
print(f"three_passes : {1000 * slow:>7.2f} ms")
print(f"نسبت         : {slow / fast:>7.2f}")
```

```text-approx
one_pass     :    0.17 ms
three_passes :    0.57 ms
نسبت         :    3.24
```

<div dir="rtl">

**سه برابرِ شمارنده، حدودِ سه برابرِ ساعت.** اگر سرویسی داری که این تابع را روزی ده میلیون بار صدا می‌زند، آن ضریبِ `3` تفاوتِ یک سرور با سه سرور است. **`Big-O` این را به تو نمی‌گوید و قرار هم نیست بگوید — ولی تو باید بدانی که نمی‌گوید.**

## ۵. سه چیزی که `Big-O` نمی‌گوید

اولی و دومی را دیدیم: **ثابت‌ها** و **`n`های کوچک**. سومی از همه پنهان‌تر است: **کدام ورودی؟**

</div>

```python
def counted_duplicate(values):
    comparisons = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            comparisons += 1
            if values[i] == values[j]:
                return values[i], comparisons
    return None, comparisons


n = 1_000
worst = list(range(n))                       # هیچ تکراری ندارد
best = [7, 7] + list(range(100, 100 + n - 2))   # تکراری در همان اول
print("بهترین ورودی :", counted_duplicate(best)[1], "مقایسه")
print("بدترین ورودی:", counted_duplicate(worst)[1], "مقایسه")
print("نسبت        :", counted_duplicate(worst)[1] // counted_duplicate(best)[1])
```

```text
بهترین ورودی : 1 مقایسه
بدترین ورودی: 499500 مقایسه
نسبت        : 499500
```

<div dir="rtl">

**یک تابع، یک `n`، و دو عدد که نیم میلیون برابر با هم فرق دارند.**

وقتی می‌گوییم `first_duplicate` مرتبه‌اش `O(n²)` است، **داریم دربارهٔ بدترین ورودی حرف می‌زنیم** — و این یک انتخاب است که باید اعلام شود. سه پرسشِ کاملاً متفاوت وجود دارد: بدترین ورودی چه می‌کند، ورودیِ متوسط چه می‌کند، و **ورودی‌ای که واقعاً به دستِ تو می‌رسد** چه می‌کند.

فعلاً همین‌قدر بدان که این سه پرسشِ متفاوت‌اند و **در این ترم همه‌جا بدترین حالت را گزارش می‌کنیم و صریح می‌گوییم که همان است.** ترمِ ۳ یک فصلِ کامل به تفاوتِ این سه اختصاص دارد.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک تابعِ ثابت روی دو ورودیِ متفاوت با `n` یکسان. **در کدام بازهٔ `n`؟** فقط `n = 1000` — و اینجا یک اندازه کافی است، چون ادعا دربارهٔ رشد نیست، دربارهٔ **وابستگی به شکلِ ورودی** است. **با چند تکرار، و کمینه یا میانگین؟** یک اجرا؛ شمارش قطعی است.

## ۶. `Θ` و `Ω`، خیلی کوتاه

`Big-O` یک **سقف** است. دو خواهر هم دارد که در متن‌های انگلیسی می‌بینی‌شان:

- **`Ω(f(n))`** یک **کف** است: کار دستِ‌کم به این اندازه هست.
- **`Θ(f(n))`** یعنی هم سقف و هم کف — یعنی کار **دقیقاً** با همین شکل می‌رود.

در عمل تقریباً همه `O` می‌نویسند حتی وقتی منظورشان `Θ` است، و این هم مشکلِ بزرگی نیست چون تقریباً همیشه تنگ‌ترین سقفِ ممکن را می‌نویسند. **ولی به این معناست که جملهٔ «مرتبه‌اش `O(n²)` است» از نظرِ فنی برای یک الگوریتمِ `O(n)` هم درست است** — یک الگوریتمِ خطی هم از `n²` بیشتر نمی‌شود. **درست ولی بی‌فایده**، و برای همین قاعدهٔ نانوشته این است که همیشه تنگ‌ترین کران را بنویسی.

> 🔧 **اگر کار نکرد:** وسوسه می‌شوی نردبانِ اندازه‌ها را از صفر شروع کنی. نکن:

</div>

```python
try:
    print(three_passes([]) / one_pass([]))
except ZeroDivisionError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
ZeroDivisionError: division by zero
```

<div dir="rtl">

**`n = 0` یک اندازهٔ منحط است:** هر ستونِ نسبتی رویش می‌شکند، و مهم‌تر اینکه دو برابرِ صفر باز هم صفر است، پس اصلاً روی نردبانِ دوبرابری نمی‌نشیند. **نردبان همیشه از عددی مثبت شروع می‌شود** — و ترجیحاً از عددی که آن‌قدر بزرگ باشد که جملهٔ غالب واقعاً غالب شده باشد.

> 🤖 **از دستیارت بپرس:** «چرا در `Big-O` جمله‌های کوچک‌تر و ضریب‌های ثابت حذف می‌شوند؟» بعد این را هم بپرس: **«اگر الگوریتمِ الف `O(n)` باشد با ضریبِ ۱۰۰۰ و الگوریتمِ ب `O(n²)` با ضریبِ ۱، از کدام `n` به بعد الف بهتر است؟»** — جوابش یک معادلهٔ ساده است و **دقیقاً موضوعِ فصلِ ۹**؛ اگر خودت حسابش کنی، آن فصل برایت تأیید می‌شود نه غافلگیری.

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `Big-O` | بیگ اُ | سقفِ رشدِ هزینه در `n`های بزرگ، بدونِ ثابت‌ها |
| dominant term | دامیننت ترم | جمله‌ای که در `n`های بزرگ بقیه را می‌بلعد |
| constant factor | کانستنت فکتور | ضریبی که به `n` بستگی ندارد و `Big-O` نمی‌بیندش |
| `Θ` | تتا | هم سقف و هم کف؛ رشد دقیقاً با همین شکل |
| `Ω` | اُمگا | کفِ رشد؛ کار دستِ‌کم این‌قدر هست |
| tight bound | تایت باند | تنگ‌ترین سقفی که هنوز درست است |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: سه چیزی که `Big-O` عمداً نمی‌گوید چیستند؟

**تمرینِ اجباری:** تابعِ `work` را به `n**3 + 1000 * n**2` تغییر بده و جدولِ سهم‌ها را دوباره بساز. **سؤالِ اصلی: از کدام `n` به بعد سهمِ `n³` از نصف بیشتر می‌شود؟** جوابت باید یک عدد باشد. بعد بگو اگر `n`ِ واقعیِ تو همیشه کمتر از آن عدد باشد، نوشتنِ «این `O(n³)` است» چه چیزی را دربارهٔ کدِ تو به خواننده می‌گوید — و چه چیزی را پنهان می‌کند.

**تمرینِ ستاره‌دار ⭐:** یک تابعِ `four_passes` بنویس و با `one_pass` و `three_passes` یک جدولِ سه‌ستونی بساز. **هر سه `O(n)` هستند.** حالا سؤال: با شمارنده می‌شود این سه را از هم تشخیص داد و با ساعت هم — پس **دقیقاً چه چیزی را `Big-O` از دست می‌دهد که این دو ابزار از دست نمی‌دهند؟** و برعکس: **`Big-O` چه چیزی به تو می‌دهد که آن جدولِ سه‌ستونی نمی‌دهد؟** جوابِ دومی سخت‌تر است و کلِ درسِ این فصل در آن است.

## در فصل بعد

`Big-O` یک پیش‌بینی است و ما هنوز هیچ پیش‌بینی‌ای را آزمون نکرده‌ایم. **فصلِ بعد پروتکلِ امضای این دوره را می‌سازد:** جدول بگیر، مرتبه را اعلام کن، **معیارِ پذیرش را قبل از اجرا بنویس**، اندازهٔ بعدی را پیش‌بینی کن، اجرایش کن، خطای نسبی را گزارش کن.

و همان‌جا یک پیش‌بینی را عمداً می‌شکنیم: **یک تابع، یک پروتکل، دو بازهٔ `n` — خطای `33.2` درصد و خطای `5.9` درصد.** اولی رد می‌شود و دومی قبول، و تفاوتشان فقط در این است که جدول را کجا گرفته‌ایم.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t1/s07-big-o (یادستان, Yaadestan)
