# فصل ۰۵ — `O(n²)`ی که در یک حلقهٔ بی‌گناه پنهان است

<div dir="rtl">

# فصل ۰۵ — `O(n²)`ی که در یک حلقهٔ بی‌گناه پنهان است

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

`insert(0, x)` یک تلهٔ **آشکار** است. این فصل دربارهٔ تله‌های نامرئی است: **چهار تکه کد که هیچ‌کدام حلقهٔ تودرتوی آشکار ندارند و هر چهارتا `O(n²)` هستند** — یا دستِ‌کم می‌توانند باشند.

برای هر چهارتا جدول می‌گیریم. یکی از آن‌ها **بر خلافِ همهٔ کتاب‌ها خطی درمی‌آید**، و همان‌جا می‌بینی چرا این دوره اصرار دارد اول اندازه بگیری. آخرِ فصل یک **قاعدهٔ تشخیص** درمی‌آید که با آن می‌شود این تله را در کدِ خودت پیدا کرد.

![چرخ‌دنده‌ای پنهان که برای هر دندانهٔ دستهٔ بیرونی یک دورِ کامل می‌زند](/lesson-assets/t2-s05-accidental-quadratic/prompt/01-image-innocent-loop.png)

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

- چهار شکلِ رایجِ `O(n²)`ِ تصادفی را در کد بشناسی
- قاعدهٔ تشخیص را روی کدِ خودت به‌کار ببری
- بگویی چرا یکی از این چهارتا روی پایتونِ امروز خطی است و چرا نباید رویش حساب کرد

## قبل از شروع

**از فصلِ ۴:** هزینهٔ درج و حذف بر حسبِ محلش، و اینکه `list` جابه‌جا می‌کند.

</div>

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

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-2-arrays-and-lists/session-05-accidental-quadratic.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. شکلِ اول: `in` روی یک `list`، داخلِ حلقه

`x in known` یک عبارتِ کوتاه و بی‌آزار است. **ولی اگر `known` یک `list` باشد، این عبارت از ابتدا تا آخرش می‌گردد.** داخلِ یک حلقهٔ `n`تایی، همین می‌شود `n` بار گشتن.

> 🤔 **اول حدس بزن:** ستونِ نسبتِ این کد با دو برابر شدنِ `n` چه عددی می‌دهد؟

</div>

```python
rng = random.Random(SEED)


def count_shared(items, known):
    hits = 0
    for x in items:
        if x in known:              # این خط، خودش یک حلقه است
            hits += 1
    return hits


def counted_shared(items, known):
    """همان کار، با شمارندهٔ صریح به‌جای in."""
    ops = 0
    for x in items:
        for y in known:
            ops += 1
            if x == y:
                break
    return ops


LADDER = [250, 500, 1_000, 2_000]
pairs = {n: (rng.sample(range(4 * n), n), rng.sample(range(4 * n), n)) for n in LADDER}
print("— شمارشِ مقایسه‌ها")
table([(n, counted_shared(*pairs[n])) for n in LADDER], "مقایسه", ",d")
```

```text
— شمارشِ مقایسه‌ها
         n            مقایسه     نسبت به سطر قبل
       250            55,553                   —
       500           218,729                3.94
     1,000           873,254                3.99
     2,000         3,514,059                4.02
```

<div dir="rtl">

**`4.00`. شمارنده قطعی است و جای شک نمی‌گذارد.**

> 🌱 **ریشه‌اش کجاست:** چرا دقیقاً چهار برابر؟ چون هر یک از `n` عضوِ `items` تا `n` خانهٔ `known` را می‌بیند، و `n` بار `n` می‌شود `n²`. همین شکل در بخش‌های ۲ و ۴ کمی فرق دارد: آن‌جا ظرف در هر دور یکی بزرگ‌تر می‌شود، پس کلِ کار `1 + 2 + … + n` است که با باز کردن و فاکتور گرفتن به `n(n+1)/2` تبدیل می‌شود — یعنی **نصفِ `n²` به‌علاوهٔ نصفِ `n`**. باز کردن و فاکتور گرفتن در [ریشه ترمِ ۳ فصل ۴](/courses/risheh/lessons/term-3-algebra/session-04-distribute-factor) ساخته می‌شود. **در هر دو حالت جملهٔ `n²` غالب است و برای همین نسبت به `4` می‌رسد، نه به `2`.**

**راهِ حلش ظرفِ دیگری است که هزینهٔ پرسشِ «هست یا نه؟» را ثابت می‌کند. ساختش موضوعِ ترمِ ۳ است** — این فصل فقط کارش این است که تشخیصش بدهی.

## ۲. شکلِ دوم: ساختنِ رشته با `+=`

هر کتابی می‌گوید `s += "x"` در حلقه `O(n²)` است، چون رشته در پایتون تغییرناپذیر است و هر بار نسخهٔ تازه‌ای ساخته می‌شود.

> 🤔 **اول حدس بزن:** بنویس ستونِ نسبتش را چه عددی انتظار داری: `2` یا `4`؟

</div>

```python
def grow_plain(n):
    s = ""
    for _ in range(n):
        s += "x"
    return s


def grow_with_shadow(n):
    """همان حلقه، فقط یک ارجاعِ دومِ زنده به رشته هم نگه می‌دارد."""
    s = ""
    shadow = s
    for _ in range(n):
        s += "x"
        shadow = s
    return s


TEXT = [20_000, 40_000, 80_000, 160_000]
print("جوابِ دو نسخه یکی است؟", grow_plain(2_000) == grow_with_shadow(2_000))
print("\n— s += 'x'")
table([(n, 1000 * clock(lambda k=n: grow_plain(k), repeat=2)) for n in TEXT],
      "زمان (ms)", ",.2f")
print("\n— همان حلقه، با یک ارجاعِ دومِ زنده")
table([(n, 1000 * clock(lambda k=n: grow_with_shadow(k), repeat=2)) for n in TEXT],
      "زمان (ms)", ",.2f")
```

```text-approx
جوابِ دو نسخه یکی است؟ True

— s += 'x'
         n         زمان (ms)     نسبت به سطر قبل
    20,000              1.96                   —
    40,000              3.95                2.01
    80,000              8.17                2.07
   160,000             15.49                1.90

— همان حلقه، با یک ارجاعِ دومِ زنده
         n         زمان (ms)     نسبت به سطر قبل
    20,000              7.81                   —
    40,000             26.85                3.44
    80,000             82.95                3.09
   160,000            332.86                4.01
```

<div dir="rtl">

**جدولِ اول `2` می‌دهد، نه `4`. کتاب‌ها اشتباه نمی‌گویند؛ فقط دربارهٔ پایتونِ امروز حرف نمی‌زنند.**

پایتون یک میان‌بر دارد: اگر **هیچ‌کس دیگری** به آن رشته ارجاع نداشته باشد، به‌جای ساختنِ نسخهٔ تازه، همان‌جا بزرگش می‌کند. جدولِ دوم دقیقاً همین را ثابت می‌کند: **یک متغیرِ اضافه که فقط نگاه می‌کند، ستونِ نسبت را از `2` به حدودِ `4` می‌برد.** هیچ چیزِ دیگری عوض نشد.

**پس این میان‌بر یک تضمین نیست، یک شانس است** — و شانسی که با یک خط کدِ کاملاً بی‌ربط از دست می‌رود. اگر رشته‌ای را در حلقه می‌سازی، `"".join(parts)` را به‌کار ببر: **همیشه خطی است و به هیچ شرطی بند نیست.**

## ۳. شکلِ سوم: `del items[0]` مکرر

</div>

```python
def drain_front(n):
    items = list(range(n))
    while items:
        del items[0]
    return len(items)


def drain_back(n):
    items = list(range(n))
    while items:
        del items[-1]
    return len(items)


DEL = [10_000, 20_000, 40_000, 80_000]
print("— del items[0]")
table([(n, 1000 * clock(lambda k=n: drain_front(k), repeat=2)) for n in DEL],
      "زمان (ms)", ",.2f")
print("\n— del items[-1]")
table([(n, 1000 * clock(lambda k=n: drain_back(k), repeat=2)) for n in DEL],
      "زمان (ms)", ",.2f")
```

```text-approx
— del items[0]
         n         زمان (ms)     نسبت به سطر قبل
    10,000             19.79                   —
    20,000             78.00                3.94
    40,000            324.74                4.16
    80,000          1,212.42                3.73

— del items[-1]
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.30                   —
    20,000              0.60                1.99
    40,000              1.27                2.10
    80,000              2.74                2.16
```

<div dir="rtl">

**`4` در برابرِ `2`، دقیقاً مثلِ `pop(0)` در برابرِ `pop()` در فصلِ قبل.** یک نویسه اختلاف — `0` یا `-1` — و دو مرتبهٔ متفاوت.

## ۴. شکلِ چهارم: `items = items + [x]`

این یکی موذی‌ترینشان است، چون **خیلی شبیهِ `append` به‌نظر می‌رسد.**

</div>

```python
def grow_by_concat(n):
    items = []
    for i in range(n):
        items = items + [i]         # یک list تازه، هر بار
    return items


def grow_by_append(n):
    items = []
    for i in range(n):
        items.append(i)             # همان list، هر بار
    return items


CONCAT = [4_000, 8_000, 16_000, 32_000]
print("جوابِ دو نسخه یکی است؟", grow_by_concat(500) == grow_by_append(500))
print("\n— items = items + [x]")
table([(n, 1000 * clock(lambda k=n: grow_by_concat(k), repeat=2)) for n in CONCAT],
      "زمان (ms)", ",.2f")
print("\n— items.append(x)")
table([(n, 1000 * clock(lambda k=n: grow_by_append(k), repeat=2)) for n in CONCAT],
      "زمان (ms)", ",.2f")
```

```text-approx
جوابِ دو نسخه یکی است؟ True

— items = items + [x]
         n         زمان (ms)     نسبت به سطر قبل
     4,000             14.55                   —
     8,000             69.79                4.80
    16,000            324.32                4.65
    32,000          1,169.11                3.60

— items.append(x)
         n         زمان (ms)     نسبت به سطر قبل
     4,000              0.11                   —
     8,000              0.27                2.39
    16,000              0.54                2.02
    32,000              0.84                1.56
```

<div dir="rtl">

**`4` در برابرِ `2`، با خروجیِ کاملاً یکسان.** `items + [i]` یک `list` تازه می‌سازد و همه‌چیز را در آن کپی می‌کند؛ `append` همان ظرف را نگه می‌دارد.

> ⚠️ **مواظب باش:** `items += [x]` — با علامتِ مساوی — رفتارِ `append` را دارد نه رفتارِ `+`. **سه شکلِ نوشتاریِ نزدیک به هم، دو مرتبهٔ متفاوت.** این‌جا هم مثلِ شکلِ دوم، تفاوت در این است که ظرف **همان یکی می‌ماند** یا **دوباره ساخته می‌شود**.

## ۵. قاعدهٔ تشخیص

هر چهار شکل یک ساختارِ مشترک دارند و این ساختار را می‌شود در یک جمله نوشت:

> **یک عملِ `O(n)` داخلِ یک حلقهٔ `n`تایی.**

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

| عمل | مرتبه | چرا | کجا اندازه گرفته شد |
|---|---|---|---|
| `x in values` روی `list` | `O(n)` | از ابتدا می‌گردد | همین فصل، بخشِ ۱ |
| `values.index(x)` | `O(n)` | همان | ت۲ف۱ بخشِ ۳ |
| `values.insert(0, x)` · `values.pop(0)` | `O(n)` | همه را جابه‌جا می‌کند | ت۲ف۴ بخش‌های ۱ تا ۳ |
| `del values[0]` | `O(n)` | همان | همین فصل، بخشِ ۳ |
| `a + b` روی `list` یا رشته | `O(n)` | ظرفِ تازه می‌سازد و کپی می‌کند | همین فصل، بخش‌های ۲ و ۴ |
| `list(values)` · `values[:]` | `O(n)` | کپیِ کامل | ت۲ف۲ بخشِ ۴ (فقط `list(values)`) |
| `values.append(x)` | `O(1)` `amortised` | فقط انتها | ت۲ف۳ بخشِ ۵ |
| `values.pop()` · `del values[-1]` | `O(1)` | فقط انتها | ت۲ف۴ بخشِ ۳ · همین فصل، بخشِ ۳ |
| `values[i]` | `O(1)` | آدرس را حساب می‌کند | ت۲ف۱ بخشِ ۱ |
| `len(values)` | `O(1)` | طول را جدا نگه می‌دارد | **نسنجیده** |

**یک سطر «نسنجیده» علامت خورده و این عمدی است.** `len(values)` جوابش بدیهی به‌نظر می‌رسد — و **این دوره اندازه‌اش نگرفته**. `values[:]` هم همین‌طور: فقط `list(values)` سنجیده شد. مخصوصاً `len`: اینکه پایتون طول را جدا نگه می‌دارد به‌جای اینکه هر بار بشمارد، یک **جزئیاتِ پیاده‌سازی** است، نه یک قانون. **در جدولِ خودت هم همین کار را بکن؛ خانهٔ نقل‌شده را با خانهٔ اندازه‌گیری‌شده یک شکل ننویس.** (ترمِ ۶ فصلِ ۲ کلِ یک بخش را به همین می‌دهد.)

**و بازهٔ `n` هم بخشی از این جدول است:** سطرهای اندازه‌گیری‌شده در بازه‌ای بینِ حدودِ ۲۵۰ و ۱۶۰٬۰۰۰ عضو گرفته شده‌اند. **زیرِ چند ده عضو هیچ‌کدام از این مرتبه‌ها دیده نمی‌شوند** — همان درسِ ترمِ ۱ فصلِ ۵.

**و مهم‌ترین نکتهٔ این جدول ستونِ مرتبه نیست، ستونِ اول است:** شش سطرِ اول همه یک خط کدِ کوتاه‌اند. هیچ‌کدامشان شبیهِ حلقه نیستند.

> ✅ **چک کن:** `count_shared` را طوری تغییر بده که `known` را قبل از حلقه به یک `set` تبدیل کند و جدولِ زمانش را بگیر. **ستونِ نسبت باید از `4` به حدودِ `2` بیفتد.** فعلاً همین‌قدر بدان که `set` پرسشِ عضویت را ارزان می‌کند؛ **ترمِ ۳ نشان می‌دهد چطور، و هزینهٔ پنهانش چیست.**

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** چهار الگوی `O(n²)`، هرکدام با نسخهٔ خطیِ متناظرش که خروجیِ یکسان می‌دهد. **در کدام بازهٔ `n`؟** هر شکل در بازهٔ خودش — از ۲۵۰ تا ۲٬۰۰۰ برای شمارش، و از ۴٬۰۰۰ تا ۱۶۰٬۰۰۰ برای زمان، **چون بازه را طوری انتخاب کردیم که هر جدول در حدودِ یک ثانیه تمام شود**. **با چند تکرار، و کمینه یا میانگین؟** دو تکرار به‌علاوهٔ گرم‌کننده، کمینه، و هر اجرا ورودیِ تازهٔ خودش را می‌سازد.

> 🔧 **اگر کار نکرد:** موقعِ درست کردنِ شکلِ چهارم، رایج‌ترین اشتباه این است که `+` را نگه داری و فقط براکت را برداری:

</div>

```python
try:
    items = [1, 2, 3]
    items = items + 4
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: can only concatenate list (not "int") to list
```

<div dir="rtl">

پیام صریح است: `+` روی `list` فقط `list` قبول می‌کند. **و همین سخت‌گیری یادآورِ همان چیزی است که گران بود** — `items + [4]` یک ظرفِ سوم می‌سازد. اگر یک عضو می‌خواهی اضافه کنی، `append` کارِ درست است.

> 🤖 **از دستیارت بپرس:** «چه عملیاتی در پایتون `O(n)` هستند ولی شبیهِ یک عملِ ساده به‌نظر می‌رسند؟» بعد این را هم بپرس: **«چرا `s += "x"` در حلقه گاهی خطی است و گاهی درجه‌دو؟»** — جوابِ درست به تعدادِ ارجاع‌های زندهٔ آن رشته برمی‌گردد، و اگر دستیارت فقط گفت «همیشه درجه‌دو است»، **جدولِ بخشِ ۲ را جلویش بگذار.**

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| accidental quadratic | اکسیدنتال کوادراتیک | کدی که بدونِ حلقهٔ تودرتوی آشکار، `O(n²)` است |
| hidden loop | هیدن لوپ | عملی که در یک خط نوشته می‌شود ولی داخلش روی کلِ داده می‌گردد |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: قاعدهٔ تشخیص را در یک جمله بنویس.

**تمرینِ اجباری:** این تابع را بخوان و **قبل از هر اجرایی** مرتبه‌اش را اعلام کن، و بنویس کدام خط مقصر است:

</div>

```python
def unique_in_order(values):
    seen = []
    out = ""
    for v in values:
        if v not in seen:
            seen.append(v)
            out = out + str(v) + ","
    return out
```

<div dir="rtl">

بعد جدولِ چهار اندازه‌ای‌اش را بگیر و ببین اعلامت درست بود یا نه. **حالا نسخهٔ خطی‌اش را بنویس و با `==` ثابت کن خروجی عوض نشده.** جوابت باید بگوید کدام‌یک از دو خطِ مقصر سهمِ بیشتری داشت — و برای این باید هر کدام را جدا درست کنی و جدا اندازه بگیری.

**تمرینِ ستاره‌دار ⭐:** یک تابع بنویس که در بازهٔ `n` بینِ هزار و هشت هزار ستونِ نسبتِ `2.00` بدهد ولی از `n = 100,000` به بعد به `4` برسد. (راهنمایی: عملِ `O(n)` را فقط گاهی صدا بزن، نه در هر دورِ حلقه.) بعد **همان تابع را با پروتکلِ خودت لو بده**: نشان بده کدام تصمیمِ اندازه‌گیری — بازه، شمارنده، یا جدولِ دوم — جلوی این تله را می‌گیرد.

## در فصل بعد

هر بار که هزینهٔ جابه‌جایی را دیدیم، یک فکر پیش آمده: **اگر ظرفی داشتیم که خانه‌هایش لازم نبود کنارِ هم باشند، هیچ‌کدام از این جابه‌جایی‌ها لازم نمی‌شد.**

فصلِ بعد آن ظرف را می‌سازد — `linked list` — و روی همان کاری که قرار است در آن برنده باشد اندازه‌اش می‌گیرد. **نتیجه منفی است**، و ما همان‌قدر پررنگ گزارشش می‌کنیم که یک نتیجهٔ مثبت را: در یک آزمایش، `list` بیش از چهل برابر سریع‌تر درمی‌آید. دلیلش هم `Big-O` نیست.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t2/s05-accidental-quadratic (یادستان, Yaadestan)
