# فصل ۰۶ — شش منحنی که تقریباً همه‌چیز را توضیح می‌دهند

<div dir="rtl">

# فصل ۰۶ — شش منحنی که تقریباً همه‌چیز را توضیح می‌دهند

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

تقریباً هر کدی که در عمرت بنویسی یا بخوانی، یکی از **شش شکلِ رشد** را دارد. این فصل هر شش‌تا را با شمارنده می‌سازد، نامِ رسمی‌شان را می‌گذارد، و بعد یک سؤال از همه‌شان می‌پرسد: **اگر `n` هزار برابر شود، کار چند برابر می‌شود؟**

جواب‌ها این‌ها هستند: **`1`، `2`، `1,000`، `2,000`، `1,001,000` — و برای ششمی، عددی با `300,729` رقم.**

آن سطرِ آخر شوخی نیست و توضیحش این است که چرا بعضی مسئله‌ها با هیچ کامپیوترِ سریع‌تری حل نمی‌شوند.

![شش لولهٔ شیشه‌ای هم‌قد که مایع در هرکدام تا ارتفاعِ کاملاً متفاوتی بالا آمده](/lesson-assets/t1-s06-orders-of-growth/prompt/01-image-six-columns.png)

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

- شش مرتبهٔ اصلیِ رشد را با نامِ `O(...)` بشناسی و نمونهٔ کدِ هرکدام را بنویسی
- از روی ستونِ نسبت بگویی یک کد کدام شکل را دارد
- شمارشِ عملیات را به زمانِ تخمینی روی ماشینِ خودت تبدیل کنی
- بگویی چرا `O(2^n)` را نمی‌شود با سخت‌افزارِ بهتر نجات داد

## قبل از شروع

**از فصلِ ۵:** جدولِ دوبرابری و قاعدهٔ خواندنِ ستونِ نسبت. **این فصل روی همان قاعده اسم می‌گذارد.**

**از فصلِ ۴:** شمارندهٔ عملیات.

نمادِ `O(...)` را از این فصل به‌کار می‌بریم، **ولی تعریفِ دقیقش فصلِ بعد است.** فعلاً همین‌قدر بدان که `O(n²)` یعنی «کار با مربعِ `n` می‌رود»؛ فصلِ ۷ می‌گوید این جمله دقیقاً چه چیزی را ادعا می‌کند و چه چیزی را نمی‌کند.

</div>

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

<div dir="rtl">

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

## ۱. پنج منحنیِ اول، با شمارنده

پنج تابعِ کوچک می‌نویسیم که هرکدام یک شکلِ رشدِ متفاوت دارند، و همه‌شان را روی یک نردبانِ دوبرابری می‌بریم.

> 🤔 **اول حدس بزن:** برای `O(n log n)` بنویس ستونِ نسبت چه عددی می‌دهد. بین `2` و `4` است یا بیرونِ این بازه؟ و آیا با بزرگ شدنِ `n` بالا می‌رود یا پایین؟

</div>

```python
def constant_work(values):
    """یک کار، هرچقدر هم که ورودی بزرگ باشد."""
    return 1


def log_work(values):
    """هر بار نصف، تا یکی بماند."""
    ops, size = 0, len(values)
    while size > 1:
        size //= 2
        ops += 1
    return ops


def linear_work(values):
    """یک کار به‌ازای هر عضو."""
    ops = 0
    for _ in values:
        ops += 1
    return ops


def linearithmic_work(values):
    """به‌اندازهٔ تعدادِ نصف‌شدن‌ها، یک بار کلِ داده را می‌بیند."""
    ops, width = 0, 1
    while width < len(values):
        for _ in values:
            ops += 1
        width *= 2
    return ops


def quadratic_work(values):
    """هر عضو با هر عضوِ بعد از خودش."""
    ops = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            ops += 1
    return ops


CURVES = [("O(1)", constant_work), ("O(log n)", log_work), ("O(n)", linear_work),
          ("O(n log n)", linearithmic_work), ("O(n²)", quadratic_work)]
STEPS = [8, 16, 32, 64]
counts = {name: [fn(list(range(n))) for n in STEPS] for name, fn in CURVES}

print("شمارشِ عملیات")
print(f"{'n':>8}" + "".join(f"{name:>12}" for name, _ in CURVES))
for row, n in enumerate(STEPS):
    print(f"{n:>8}" + "".join(f"{counts[name][row]:>12,}" for name, _ in CURVES))

print("\nنسبتِ هر سطر به سطرِ قبل")
for row in range(1, len(STEPS)):
    label = f"{STEPS[row - 1]} → {STEPS[row]}"
    print(f"{label:>8}" + "".join(
        f"{counts[name][row] / counts[name][row - 1]:>12.2f}" for name, _ in CURVES))
```

```text
شمارشِ عملیات
       n        O(1)    O(log n)        O(n)  O(n log n)       O(n²)
       8           1           3           8          24          28
      16           1           4          16          64         120
      32           1           5          32         160         496
      64           1           6          64         384       2,016

نسبتِ هر سطر به سطرِ قبل
  8 → 16        1.00        1.33        2.00        2.67        4.29
 16 → 32        1.00        1.25        2.00        2.50        4.13
 32 → 64        1.00        1.20        2.00        2.40        4.06
```

<div dir="rtl">

**جدولِ دوم همان قاعدهٔ فصلِ ۵ است، این بار با اسم:**

- **`O(1)` — نسبت دقیقاً `1`.** خواندنِ خانهٔ اولِ یک فهرست، هرچقدر هم فهرست بزرگ باشد.
- **`O(log n)` — نسبت کمی بالای یک، و رو به پایین.** هر دو برابر شدنِ `n` فقط **یک قدم** اضافه می‌کند. این ارزان‌ترین چیزی است که هنوز به `n` وابسته است.
- **`O(n)` — نسبت دقیقاً `2`.** یک بار دیدنِ همهٔ داده.
- **`O(n log n)` — نسبت بینِ `2` و `3`، و رو به پایین.** چند بار دیدنِ همهٔ داده، که تعدادِ دفعاتش خودش `log n` است. **این مرتبهٔ مرتب‌سازی است** و در ترمِ ۴ کاملاً بازش می‌کنیم.
- **`O(n²)` — نسبت بالای `4` و رو به پایین به‌سمتِ `4`.** هر عضو با هر عضو.

> ✅ **چک کن:** ستونِ `O(n log n)` باید در `n = 8` عددِ `24` بدهد، یعنی `8 × 3`. آن `3` تعدادِ دفعاتی است که `1` را باید دو برابر کنی تا به `8` برسی. اگر `32` گرفتی، حلقهٔ بیرونی یک دورِ اضافه رفته — شرطِ `while width < len(values)` را چک کن.

## ۲. منحنیِ ششم

پنج منحنیِ بالا همه رام‌اند. ششمی نیست.

</div>

```python
def exponential_work(values):
    """همهٔ حالت‌های روشن-خاموشِ n عضو را یکی‌یکی می‌بیند."""
    ops = 0
    for _ in range(2 ** len(values)):
        ops += 1
    return ops


table([(n, exponential_work(list(range(n)))) for n in (2, 4, 8, 16)], "عملیات", ",d")
print("فرمول برای n = 20:", 2 ** 20, "· شمارشِ واقعی:",
      exponential_work(list(range(20))))
```

```text
         n            عملیات     نسبت به سطر قبل
         2                 4                   —
         4                16                4.00
         8               256               16.00
        16            65,536              256.00
فرمول برای n = 20: 1048576 · شمارشِ واقعی: 1048576
```

<div dir="rtl">

**به ستونِ نسبت نگاه کن: `4`، بعد `16`، بعد `256`. خودِ نسبت هم منفجر می‌شود.**

در پنج منحنیِ قبل، ستونِ نسبت به عددی می‌رسید و آنجا می‌ماند. در `O(2^n)` ستونِ نسبت هر بار **مربع** می‌شود. برای همین این تنها مرتبه‌ای است که با هیچ ماشینی نمی‌شود نجاتش داد: **ماشینِ هزار برابر سریع‌تر، فقط ده واحد به `n`ی که می‌توانی حل کنی اضافه می‌کند** — چون `2¹⁰` حدودِ هزار است.

آخرین سطر هم مهم است: **شمارشِ واقعی با فرمولِ `2^n` مو نمی‌زند.** فرمول را حدس نزدیم؛ **راستی‌آزمایی‌اش کردیم** — و از این به بعد هر جا فرمولی می‌نویسیم، همین کار را می‌کنیم.

> 🌱 **ریشه‌اش کجاست:** اینکه چرا `2^n` این‌قدر زود از کنترل خارج می‌شود و چرا شهودِ آدم همیشه کم‌برآوردش می‌کند، در [ریشه ترمِ ۴ فصل ۷](/courses/risheh/lessons/term-4-functions/session-07-exponential) با مثالِ ملموس ساخته شده. و `log` که در سه منحنیِ دیگر ظاهر شد، **دقیقاً وارونهٔ همین است** — [ریشه ترمِ ۴ فصل ۸](/courses/risheh/lessons/term-4-functions/session-08-log).

## ۳. از شمارش تا زمان

شمارش مستقل از ماشین است، ولی گاهی می‌خواهی بدانی این کار **روی ماشینِ خودت** چقدر طول می‌کشد. برای این کار یک عدد لازم داری: **ماشینِ تو در ثانیه چند عملِ ساده انجام می‌دهد؟** آن را اندازه می‌گیریم و بقیه یک تقسیم است.

</div>

```python
import math

start = time.perf_counter()
tick = 0
for _ in range(2_000_000):
    tick += 1
RATE = 2_000_000 / (time.perf_counter() - start)
YEAR = 365 * 24 * 3600


def human_time(seconds):
    if seconds * 1e6 < 1:
        return "زیرِ یک میکروثانیه"
    if seconds < 1e-3:
        return f"{seconds * 1e6:,.0f} میکروثانیه"
    if seconds < 1:
        return f"{seconds * 1e3:,.1f} میلی‌ثانیه"
    if seconds < 3600:
        return f"{seconds:,.1f} ثانیه"
    if seconds < 30 * 24 * 3600:
        return f"{seconds / 3600:,.1f} ساعت"
    if seconds / YEAR < 1e6:
        return f"{seconds / YEAR:,.0f} سال"
    return f"{seconds / YEAR:.1e} سال"


def halvings(n):
    """چند بار باید یک را دو برابر کرد تا به n برسیم — همان log2 رو به بالا."""
    steps, size = 0, 1
    while size < n:
        size *= 2
        steps += 1
    return steps


FORMULAS = [
    ("O(1)", lambda n: 1),
    ("O(log n)", halvings),
    ("O(n)", lambda n: n),
    ("O(n log n)", lambda n: n * halvings(n)),
    ("O(n²)", lambda n: n * (n - 1) // 2),
    ("O(2^n)", lambda n: 2 ** n),
]

print(f"سرعتِ اندازه‌گیری‌شدهٔ این ماشین: {RATE:,.0f} عمل در ثانیه\n")
print(f"{'مرتبه':>12}" + "".join(f"{'n=' + str(n):>22}" for n in (10, 100, 1000)))
for name, f in FORMULAS:
    cells = "".join(f"{human_time(f(n) / RATE):>22}" for n in (10, 100, 1000))
    print(f"{name:>12}{cells}")
```

```text-approx
سرعتِ اندازه‌گیری‌شدهٔ این ماشین: 13,146,029 عمل در ثانیه

       مرتبه                  n=10                 n=100                n=1000
        O(1)    زیرِ یک میکروثانیه    زیرِ یک میکروثانیه    زیرِ یک میکروثانیه
    O(log n)    زیرِ یک میکروثانیه    زیرِ یک میکروثانیه    زیرِ یک میکروثانیه
        O(n)    زیرِ یک میکروثانیه          8 میکروثانیه         76 میکروثانیه
  O(n log n)          3 میکروثانیه         53 میکروثانیه        761 میکروثانیه
       O(n²)          3 میکروثانیه        377 میکروثانیه       38.0 میلی‌ثانیه
      O(2^n)         78 میکروثانیه           3.1e+15 سال          2.6e+286 سال
```

<div dir="rtl">

**در `n = 10` هر شش مرتبه در چند میکروثانیه تمام می‌شوند و انتخاب بینشان بی‌معناست. در `n = 100` یکی‌شان از عمرِ جهان بیشتر طول می‌کشد.**

> ⚠️ **مواظب باش:** این جدول **حساب شده است، نه اندازه‌گیری‌شده** — به‌جز عددِ سرعتِ ماشین که واقعاً گرفته شد. ما `O(2^n)` را در `n = 1000` اجرا نکردیم؛ شمارشش را از فرمول برداشتیم و تقسیم بر سرعت کردیم. **جدولی که برون‌یابی است باید خودش این را بگوید**، وگرنه خواننده آن را به‌جای مشاهده می‌گیرد. یک ایرادِ صادقانهٔ دیگر هم دارد: «عمل» در همهٔ این مرتبه‌ها هزینهٔ یکسانی ندارد و ما فرض کردیم دارد. **فصلِ ۹ نشان می‌دهد این فرض کجا می‌شکند.**

## ۴. اگر `n` هزار برابر شود

سؤالی که در کارِ واقعی بیشتر از همه پرسیده می‌شود این نیست که «الان چقدر طول می‌کشد»؛ این است که **«اگر داده‌ام ده یا صد یا هزار برابر شود، چه بلایی سرم می‌آید».**

</div>

```python
base, big = 1_000, 1_000_000
print(f"{'مرتبه':>12}{'کار چند برابر می‌شود؟':>28}")
for name, f in FORMULAS[:-1]:
    print(f"{name:>12}{f(big) / f(base):>28,.0f}")
digits = math.floor((big - base) * math.log10(2)) + 1
print(f"{'O(2^n)':>12}{'عددی با ' + format(digits, ',') + ' رقم':>28}")
```

```text
       مرتبه       کار چند برابر می‌شود؟
        O(1)                           1
    O(log n)                           2
        O(n)                       1,000
  O(n log n)                       2,000
       O(n²)                   1,001,000
      O(2^n)         عددی با 300,729 رقم
```

<div dir="rtl">

**این جدول را حفظ کن؛ بیشتر از هر جدولِ دیگری در این دوره به‌کارت می‌آید.**

- **`O(log n)` هزار برابر داده را با دو برابر کار جواب می‌دهد.** برای همین ساختارهای مبتنی بر نصف‌کردن این‌قدر ارزشمندند.
- **فاصلهٔ `O(n)` و `O(n log n)` فقط دو برابر است.** این عددِ کوچک تصمیم‌های زیادی را ساده می‌کند: اگر مرتب کردنِ داده مسئله‌ات را حل می‌کند، هزینه‌اش تقریباً هیچ است.
- **`O(n²)` هزار برابر داده را با یک میلیون برابر کار جواب می‌دهد.** همان چیزی که در فصلِ ۱ به‌شکلِ «سه ساعت» دیدی.
- **و `O(2^n)` عددی می‌دهد که حتی نوشتنش هم ممکن نیست.** برای همین آن سطر عدد ندارد و **تعدادِ رقم‌ها** را گزارش می‌کند.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** شش فرمولِ رشد با هم، روی یک محورِ مشترک. **در کدام بازهٔ `n`؟** شمارشِ **اندازه‌گیری‌شده** در `n = 8` تا `64` (و برای `O(2^n)` در `n = 2` تا `20`)؛ جدول‌های بخشِ ۳ و ۴ **حساب‌شده**‌اند، نه اندازه‌گیری‌شده. **با چند تکرار، و کمینه یا میانگین؟** شمارش قطعی است، پس یک اجرا؛ **تنها عددِ لرزانِ این فصل سرعتِ ماشین است** و همان یکی هم با `perf_counter` و یک حلقهٔ دو میلیونی گرفته شد.

## ۵. شکلِ منحنی‌ها

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

</div>

```python
import matplotlib.pyplot as plt

xs = list(range(1, 33))
plt.figure(figsize=(7, 4.5))
for name, f in FORMULAS:
    plt.plot(xs, [f(n) for n in xs], label=name)
plt.yscale("log")
plt.xlabel("n")
plt.ylabel("operations (log scale)")
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
print("شش منحنی روی محورِ عمودیِ لگاریتمی رسم شدند؛ n از 1 تا 32.")
```

```text
شش منحنی روی محورِ عمودیِ لگاریتمی رسم شدند؛ n از 1 تا 32.
```

<div dir="rtl">

**دو چیز در این نمودار مهم است.**

اول اینکه در `n`های کوچکِ سمتِ چپ، منحنی‌ها **به هم چسبیده‌اند** و حتی جایشان عوض می‌شود. تمامِ فصلِ ۹ دربارهٔ همان ناحیه است.

دوم اینکه `O(2^n)` روی محورِ لگاریتمی یک **خطِ راست** است. این خودش تعریفِ رشدِ نمایی است: روی محورِ لگاریتمی صاف می‌شود، چون در هر قدم در یک عددِ ثابت ضرب می‌شود.

> 🔧 **اگر کار نکرد:** اگر `n` را در جدولِ بخشِ ۳ خیلی بزرگ بگیری، پایتون سرِ تقسیم می‌ایستد:

</div>

```python
try:
    print(2 ** 2_000 / RATE)
except OverflowError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
OverflowError: int too large to convert to float
```

<div dir="rtl">

**پیام دقیقاً همان درسِ این فصل را می‌دهد:** عددِ صحیحِ پایتون سقف ندارد و `2 ** 2000` را بی‌دردسر می‌سازد، ولی **عددِ اعشاری سقف دارد** و آن عدد در آن جا نمی‌شود. راهِ درست این است که به‌جای خودِ عدد، **تعدادِ رقم‌هایش** را حساب کنی — دقیقاً کاری که در بخشِ ۴ با `math.log10` کردیم.

> 🤖 **از دستیارت بپرس:** «چرا `O(n log n)` فقط دو برابرِ `O(n)` بدتر است وقتی `n` هزار برابر می‌شود؟» بعد این را هم بپرس: **«اگر کامپیوترم هزار برابر سریع‌تر شود، برای هر یک از این شش مرتبه، بزرگ‌ترین `n`ی که در یک ثانیه حل می‌کنم چند برابر می‌شود؟»** — جوابِ `O(n)` هزار برابر است، جوابِ `O(n²)` حدودِ سی‌ودو برابر، و جوابِ `O(2^n)` **فقط ده واحد بیشتر**. همین سه عدد کلِ درسِ این فصل‌اند.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `O(1)` | اُ یک | هزینه به اندازهٔ ورودی کاری ندارد |
| `O(log n)` | اُ لگ اِن | هر دو برابر شدنِ `n` فقط یک قدم اضافه می‌کند |
| `O(n)` | اُ اِن | یک بار دیدنِ همهٔ داده |
| `O(n log n)` | اُ اِن لگ اِن | چند بار دیدنِ همهٔ داده، به تعدادِ نصف‌شدن‌ها |
| `O(n²)` | اُ اِن دو | هر عضو با هر عضو |
| `O(2^n)` | اُ دو به توانِ اِن | همهٔ حالت‌های ممکن؛ عملاً غیرقابلِ اجرا |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: کدام دو مرتبه از این شش‌تا، وقتی `n` هزار برابر می‌شود، کارشان کمتر از ده برابر می‌شود؟

**تمرینِ اجباری:** جدولِ بخشِ ۴ را برای «هزار برابر شدن» از یک پایهٔ دیگر بساز: از `n = 10` به `n = 10_000`. **آیا عددهای ستونِ آخر همان‌ها می‌مانند؟** برای `O(n)` جواب دادن راحت است؛ **برای `O(log n)`، `O(n log n)` و — کمی کمتر — `O(n²)` دقت کن** و توضیح بده چرا فقط `O(n)` است که جوابش به نقطهٔ شروع هیچ بستگی ندارد، و چرا `O(n²)` با فرمولِ دقیقِ `n(n-1)/2` عددِ `1,001,000` را به `1,111,000` تبدیل می‌کند ولی با `n²`ِ خالص عوض نمی‌شود.

**تمرینِ ستاره‌دار ⭐:** تابعی بنویس که شمارشش `O(n³)` باشد و **قبل از اجرا پیش‌بینی کن** ستونِ نسبتش چه عددی می‌دهد. بعد اجرا کن و ببین درست گفتی یا نه. حالا سؤالِ سخت: **این مرتبه را کجای جدولِ «هزار برابر» می‌گذاری؟** عددش را حساب کن و بنویس آیا به `O(n²)` نزدیک‌تر است یا به `O(2^n)`. جوابت باید توضیح بدهد که چرا فاصلهٔ `O(n²)` تا `O(n³)` با فاصلهٔ `O(n³)` تا `O(2^n)` اصلاً قابلِ مقایسه نیست.

## در فصل بعد

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

آزمایشِ اصلی‌اش یک تابع با سه جمله است — `3n² + 100n + 5000`. **در `n = 10` سهمِ جملهٔ `n²` از کلِ کار زیرِ پنج درصد است؛ در `n = 10,000` بالای ۹۹ درصد.** همان دو عدد کلِ دلیلِ وجودِ `Big-O` را می‌سازند.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t1/s06-orders-of-growth (یادستان, Yaadestan)
