# فصل ۰۳ — هزینهٔ `amortised`: عملی که گاهی گران است و همیشه ارزان

<div dir="rtl">

# فصل ۰۳ — هزینهٔ `amortised`: عملی که گاهی گران است و همیشه ارزان

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

فصلِ قبل با یک تناقض تمام شد: **بعضی از `append`ها یک کپیِ کاملِ `O(n)` هستند، پس چرا ساختنِ یک `list` بزرگ با `append` سریع است؟**

این فصل جوابش را با سه اندازه‌گیری می‌دهد. اول **تک‌تکِ چهارصد هزار `append` را جدا می‌سنجیم** و گران‌ترین‌هایشان را پیدا می‌کنیم — که هزاران برابر بقیه‌اند و همه دقیقاً روی لحظه‌های بزرگ‌شدن افتاده‌اند. بعد نشان می‌دهیم **میانگینِ همان‌ها صاف است**. و آخر می‌بینیم که اگر ظرفیت به‌جای ضرب‌شدن هر بار مقدارِ ثابتی اضافه می‌شد، کلِ ماجرا `O(n²)` می‌شد.

بینِ راه یک انتظارِ کتابِ درسی هم می‌شکند: **ظرفیتِ `list` پایتون دو برابر نمی‌شود.** ضریبش را اندازه می‌گیریم.

![سه میزِ کار با پهنای فزاینده، که بارِ میزِ میانی یکجا به میزِ پهن‌تر منتقل می‌شود](/lesson-assets/t2-s03-amortised/prompt/01-image-widening-workbench.png)

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

- بگویی «هزینهٔ `amortised`» چه چیزی را ادعا می‌کند و چه چیزی را ادعا نمی‌کند
- گران‌ترین تکِ عملیات را از میانگینِ بلندمدتش جدا کنی و **هر دو را گزارش کنی**
- نشان بدهی چرا رشدِ **ضربیِ** ظرفیت لازم است و رشدِ ثابت فاجعه است

## قبل از شروع

**از فصلِ ۲:** ظرفیت در برابرِ طول، تابعِ `capacity`، و اینکه هر بزرگ‌شدن یک کپیِ کامل است.

</div>

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

<div dir="rtl">

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

## ۱. ظرفیت واقعاً چند برابر می‌شود؟

فصلِ قبل از روی «شش پله برای هر دو برابر شدن» حدس زد که ضریبِ رشد حدودِ `1.12` است. **حالا مستقیم اندازه‌اش می‌گیریم.**

> 🤔 **اول حدس بزن:** بیشترِ کتاب‌ها می‌گویند آرایهٔ پویا ظرفیتش را **دو برابر** می‌کند. بنویس انتظار داری ستونِ «نسبت به قبلی» در این جدول چه عددی بدهد.

</div>

```python
CELL = 8
EMPTY = sys.getsizeof([])


def capacity(values):
    return (sys.getsizeof(values) - EMPTY) // CELL


steps = []
values = []
cap = 0
for i in range(20_000):
    values.append(i)
    new = capacity(values)
    if new != cap:
        steps.append(new)
        cap = new

print(f"{'ظرفیت':>10}{'نسبت به قبلی':>16}")
for a, b in zip([None] + steps[:-1], steps):
    print(f"{b:>10}" + (f"{'—':>16}" if a is None else f"{b / a:>16.3f}"))
print(f"\nتعدادِ پله‌ها تا بیست هزار: {len(steps)}")
```

```text
     ظرفیت    نسبت به قبلی
         4               —
         8           2.000
        16           2.000
        24           1.500
        32           1.333
        40           1.250
        52           1.300
        64           1.231
        76           1.188
        92           1.211
       108           1.174
       128           1.185
       148           1.156
       172           1.162
       200           1.163
       232           1.160
       268           1.155
       308           1.149
       352           1.143
       400           1.136
       456           1.140
       520           1.140
       592           1.138
       672           1.135
       760           1.131
       860           1.132
       972           1.130
      1100           1.132
      1244           1.131
      1404           1.129
      1584           1.128
      1788           1.129
      2016           1.128
      2272           1.127
      2560           1.127
      2884           1.127
      3248           1.126
      3660           1.127
      4124           1.127
      4644           1.126
      5228           1.126
      5888           1.126
      6628           1.126
      7460           1.126
      8396           1.125
      9452           1.126
     10640           1.126
     11976           1.126
     13480           1.126
     15172           1.126
     17072           1.125
     19212           1.125
     21620           1.125

تعدادِ پله‌ها تا بیست هزار: 53
```

<div dir="rtl">

**ضریب از `2.000` شروع می‌کند و به `1.125` می‌رسد و همان‌جا می‌ماند.**

پس آن جملهٔ کتابِ درسی — «ظرفیت دو برابر می‌شود» — **برای این پیاده‌سازی غلط است.** فقط دو پلهٔ اولش دو برابر است و بقیه یک‌هشتم اضافه می‌کنند.

**و این دقیقاً همان لحظه‌ای است که این دوره برایش ساخته شده:** یک جملهٔ درست‌به‌نظر، یک اندازه‌گیریِ پنج‌خطی، و یک عددِ متفاوت. **جمله را نپذیر؛ عدد را بگیر.**

ولی حالا سؤالِ مهم‌تر: **آیا `1.125` هم مثلِ `2` کافی است؟** جوابش را بخشِ ۴ می‌دهد و جواب مثبت است — چیزی که اهمیت دارد **ضربی بودن** است، نه خودِ عددِ دو.

## ۲. تک‌تکِ `append`ها

حالا سراغِ چیزی می‌رویم که تا اینجا هیچ‌وقت نکرده‌ایم: **به‌جای زمانِ کلِ حلقه، زمانِ تک‌تکِ عملیات را می‌گیریم.**

> 🤔 **اول حدس بزن:** چهارصد هزار `append` می‌زنیم و هر کدام را جدا می‌سنجیم. بنویس گران‌ترینشان نسبت به میانه چند برابر می‌شود: ده؟ صد؟ بیشتر؟

</div>

```python
N = 400_000
now = time.perf_counter

values = []
per_op = []
for i in range(N):
    start = now()
    values.append(i)
    per_op.append(now() - start)

ordered = sorted(per_op)
print(f"میانهٔ هر append   : {1e6 * ordered[N // 2]:>10.4f} µs")
print(f"گران‌ترین append   : {1e6 * ordered[-1]:>10.4f} µs")
print(f"نسبتِ گران‌ترین به میانه: {ordered[-1] / max(ordered[N // 2], 1e-9):>10,.0f} برابر")
print(f"مجموعِ همه         : {1000 * sum(per_op):>10.1f} ms")
```

```text-approx
میانهٔ هر append   :     0.1000 µs
گران‌ترین append   :   590.9000 µs
نسبتِ گران‌ترین به میانه:      5,909 برابر
مجموعِ همه         :       57.0 ms
```

<div dir="rtl">

**گران‌ترین `append` هزاران برابرِ میانه است.** پس «`append` ارزان است» به‌عنوانِ یک جملهٔ سرراست **غلط است**.

میانه آن‌قدر کوچک است که به حدِ تفکیکِ ساعت می‌خورد — همان چیزی که فصلِ ۲ ترمِ ۱ درباره‌اش هشدار داد. **برای همین این عدد را به‌عنوان یک اندازه‌گیریِ دقیق نمی‌خوانیم؛ فقط می‌گوییم «زیرِ حدِ تفکیک».** چیزی که واقعاً می‌خواهیم بدانیم این است که گران‌ها **کجا** افتاده‌اند.

## ۳. گران‌ها کجا افتاده‌اند؟

اگر توضیحِ فصلِ ۲ درست باشد، گران‌ترین `append`ها باید **دقیقاً** روی اندیس‌هایی باشند که ظرفیت در آن‌ها عوض شده. این یک پیش‌بینیِ آزمون‌پذیر است.

**یک نکتهٔ نحوی در کدِ زیر که فعلاً فقط باید بشناسی‌اش:** `sorted(..., key=...)` یعنی «مرتب کن، ولی نه بر اساسِ خودِ عضوها — بر اساسِ چیزی که این تابع از هر عضو درمی‌آورد». این‌جا عضوها اندیس‌اند و کلیدِ مرتب‌سازی `-per_op[i]` است، یعنی زمانِ هر عمل با علامتِ منفی، تا **کندترین‌ها اول بیایند**. **ترمِ ۴ فصلِ ۸ کاملاً بازش می‌کند**؛ تا آن‌جا هر بار که ببینی‌اش همین یک جمله کافی است.

</div>

```python
grown_at = []
probe = []
cap = 0
for i in range(N):
    probe.append(i)
    new = capacity(probe)
    if new != cap:
        grown_at.append(i)
        cap = new
grown = set(grown_at)

slowest = sorted(range(N), key=lambda i: -per_op[i])[:12]
total = sum(per_op)
on_growth = sum(per_op[i] for i in grown_at)
print("تعدادِ کلِ بزرگ‌شدن‌ها در این مسیر:", len(grown_at))
print("کندترین دوازده append روی این اندیس‌ها افتادند:")
print(" ", sorted(slowest))
print("چند تایشان دقیقاً روی یک بزرگ‌شدن بود؟",
      sum(1 for i in slowest if i in grown), "از ۱۲")
print(f"\nسهمِ این {len(grown_at)} عمل از تعدادِ کلِ عملیات: "
      f"{100 * len(grown_at) / N:.3f} درصد")
print(f"سهمِ همان‌ها از کلِ زمان                : {100 * on_growth / total:.1f} درصد")
del probe, per_op
```

```text-approx
تعدادِ کلِ بزرگ‌شدن‌ها در این مسیر: 78
کندترین دوازده append روی این اندیس‌ها افتادند:
  [88988, 112636, 126720, 142564, 160388, 180440, 203000, 228380, 256932, 289052, 325188, 365840]
چند تایشان دقیقاً روی یک بزرگ‌شدن بود؟ 12 از ۱۲

سهمِ این 78 عمل از تعدادِ کلِ عملیات: 0.019 درصد
سهمِ همان‌ها از کلِ زمان                : 8.9 درصد
```

<div dir="rtl">

**تقریباً همه‌شان.** گاهی هر دوازده‌تا و گاهی یازده‌تا — آن یکی معمولاً لحظه‌ای است که سیستم‌عامل وسطِ کار پرید، همان نویزِ فصلِ ۳ ترمِ ۱. **پیش‌بینی درست درآمد و توضیحِ فصلِ ۲ تأیید شد.**

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

و به فاصلهٔ اندیس‌ها نگاه کن: هرچه جلوتر می‌رویم، بزرگ‌شدن‌ها **دیرتر به دیرتر** اتفاق می‌افتند — چون ظرفیت ضربی رشد می‌کند و هر بار جای بیشتری باز می‌شود.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** اندیسِ دوازده کندترین `append` با فهرستِ اندیس‌هایی که ظرفیت در آن‌ها عوض شد — دو اندازه‌گیریِ کاملاً مستقل روی همان دنبالهٔ عملیات. **در کدام بازهٔ `n`؟** یک مسیرِ چهارصد هزارتایی، از صفر تا `n`. **با چند تکرار، و کمینه یا میانگین؟** یک اجرا و بدونِ خلاصه — چون سؤال دربارهٔ **جای** گران‌ها است نه اندازه‌شان، و جایشان قطعی است.

## ۴. پس چرا کلِ ساختن ارزان است؟

`append` گاهی `O(n)` است. **ولی آن «گاهی» چقدر است؟** جوابش را می‌شود بدونِ ساعت شمرد: مدلی می‌سازیم که فقط **تعدادِ عنصرهای جابه‌جاشده** را می‌شمارد.

> 🤔 **اول حدس بزن:** برای دو حالت حدس بزن — ظرفیتی که هر بار **دو برابر** می‌شود و ظرفیتی که هر بار **صد و بیست و هشت خانه اضافه** می‌کند. ستونِ نسبتِ هر کدام چه عددی می‌دهد؟

</div>

```python
def copied_multiplicative(n, factor=2):
    """ظرفیت هر بار در factor ضرب می‌شود."""
    cap, copied = 0, 0
    for size in range(1, n + 1):
        if size > cap:
            copied += size - 1              # همهٔ عناصرِ قبلی منتقل می‌شوند
            cap = max(cap + 1, int(cap * factor))
    return copied


def copied_constant(n, step=128):
    """ظرفیت هر بار step خانه اضافه می‌کند."""
    cap, copied = 0, 0
    for size in range(1, n + 1):
        if size > cap:
            copied += size - 1
            cap += step
    return copied


LADDER = [10_000, 20_000, 40_000, 80_000]
print("— ظرفیت هر بار دو برابر می‌شود")
table([(n, copied_multiplicative(n)) for n in LADDER], "عنصرِ منتقل‌شده", ",d")
print("\n— ظرفیت هر بار ۱۲۸ خانه اضافه می‌کند")
table([(n, copied_constant(n)) for n in LADDER], "عنصرِ منتقل‌شده", ",d")
print("\n— ظرفیت هر بار در ۱٫۱۲۵ ضرب می‌شود (کارِ خودِ پایتون)")
table([(n, copied_multiplicative(n, 1.125)) for n in LADDER], "عنصرِ منتقل‌شده", ",d")
```

```text
— ظرفیت هر بار دو برابر می‌شود
         n   عنصرِ منتقل‌شده     نسبت به سطر قبل
    10,000            16,383                   —
    20,000            32,767                2.00
    40,000            65,535                2.00
    80,000           131,071                2.00

— ظرفیت هر بار ۱۲۸ خانه اضافه می‌کند
         n   عنصرِ منتقل‌شده     نسبت به سطر قبل
    10,000           394,368                   —
    20,000         1,567,488                3.97
    40,000         6,249,984                3.99
    80,000        24,960,000                3.99

— ظرفیت هر بار در ۱٫۱۲۵ ضرب می‌شود (کارِ خودِ پایتون)
         n   عنصرِ منتقل‌شده     نسبت به سطر قبل
    10,000            88,035                   —
    20,000           178,286                2.03
    40,000           321,112                1.80
    80,000           650,744                2.03
```

<div dir="rtl">

**سه جدول، دو دنیای متفاوت.**

- **رشدِ ضربی — چه با ضریبِ `2` و چه با `1.125` — ستونِ نسبتِ `2.00` می‌دهد.** یعنی کلِ کارِ انتقال روی `n` بار `append`، خودش `O(n)` است. تقسیمش بر `n` می‌شود یک عددِ ثابت.
- **رشدِ ثابت ستونِ نسبتِ `4.00` می‌دهد:** `O(n²)`. برای هشتاد هزار عضو نزدیکِ بیست و پنج میلیون عنصر جابه‌جا می‌شود، در حالی که نسخهٔ ضربی با ضریبِ `2` حدودِ صد و سی هزارتا و با ضریبِ واقعیِ پایتون حدودِ ششصد و پنجاه هزارتا — یعنی در بدترین حالت هم نزدیکِ چهل برابر کمتر.

**و همین‌جا کلِ حرفِ فصل است: هزینهٔ `amortised` یعنی هزینهٔ کلِ یک دنبالهٔ عملیات، تقسیم بر تعدادشان.** برای `append` این عدد ثابت است، پس می‌گوییم «`append` هزینهٔ `O(1)`ِ `amortised` دارد».

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

> 🌱 **ریشه‌اش کجاست:** چرا مجموعِ انتقال‌ها `O(n)` درمی‌آید؟ چون اگر ظرفیت دو برابر شود، انتقال‌ها `1 + 2 + 4 + … + n` می‌شوند و **مجموعِ توان‌های دو همیشه کمتر از دو برابرِ آخرینشان است.** توان و دو برابر کردنِ پیاپی در [ریشه ترمِ ۱ فصل ۸](/courses/risheh/lessons/term-1-numbers/session-08-powers) ساخته می‌شود.

**و برای هر ضریبِ دیگری هم می‌شود همین را نوشت.** آخرین انتقال حدودِ `n` عضو جابه‌جا می‌کند، انتقالِ قبلی‌اش `n ÷ f`، آن یکی `n ÷ f²`، و همین‌طور. جمعِ این دنباله دو کران دارد که هر دو **ضریبی ثابت از `n`** هستند:

</div>

```text
n ÷ (f - 1)   ≤   مجموعِ کلِ انتقال‌ها   ≤   n × f ÷ (f - 1)
```

<div dir="rtl">

**دو کران لازم است، نه یک فرمولِ دقیق** — چون عددِ واقعی به این بستگی دارد که `n` کجای فاصلهٔ بینِ دو بزرگ‌شدنِ متوالی افتاده باشد. **بیایید هر دو کران را با شمارنده وارسی کنیم:**

</div>

```python
print(f"{'ضریب':>8}{'شمردهٔ واقعی':>20}{'n ÷ (f-1)':>16}{'n × f ÷ (f-1)':>18}")
for f in (2, 1.125, 1.05):
    got = copied_multiplicative(80_000, f)
    print(f"{f:>8}{got:>20,}{80_000 / (f - 1):>16,.0f}{80_000 * f / (f - 1):>18,.0f}")
```

```text
    ضریب        شمردهٔ واقعی       n ÷ (f-1)     n × f ÷ (f-1)
       2             131,071          80,000           160,000
   1.125             650,744         640,000           720,000
    1.05           1,621,558       1,600,000         1,680,000
```

<div dir="rtl">

**هر سه عددِ شمرده‌شده داخلِ کرانِ خودشان‌اند، و مهم‌ترین ستون ستونِ سوم است.** `f = 2` می‌دهد `n`، `f = 1.125` می‌دهد هشت برابرِ `n`، و `f = 1.05` بیست برابرِ `n`. **هر سه ضریبِ ثابت‌اند و ثابت یعنی `O(n)`** — ولی ثابتشان بیست برابر با هم فرق دارد، و همین دلیلِ اینکه هیچ پیاده‌سازی‌ای ضریبِ رشد را `1.05` نمی‌گذارد.

> ✅ **چک کن:** قبل از هر اجرایی، از همان کران `n ÷ (f - 1)` **پیش‌بینی کن** که `copied_multiplicative(80_000, 1.05)` چند درمی‌آید، بعد اجرایش کن و خطای پیش‌بینی‌ات را بنویس. حالا جدولِ چهار اندازه‌ایِ همان ضریب را بگیر: **عدد باید حدودِ دوازده برابرِ ضریبِ `2` باشد ولی ستونِ نسبت هنوز `2.00` بماند.** اگر ستونِ نسبت به `4` رفت، `factor` را زیرِ یک گذاشته‌ای و ظرفیت اصلاً بزرگ نمی‌شود.

## ۵. زمانِ واقعی، برای همان ادعا

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

</div>

```python
def build(n):
    out = []
    for i in range(n):
        out.append(i)
    return out


BUILD = [200_000, 400_000, 800_000, 1_600_000]
table([(n, 1000 * clock(lambda k=n: build(k), repeat=3)) for n in BUILD])
print("\nهر append به‌طورِ متوسط:",
      f"{1e9 * clock(lambda: build(1_600_000), repeat=3) / 1_600_000:.1f} نانوثانیه")
```

```text-approx
         n         زمان (ms)     نسبت به سطر قبل
   200,000               7.3                   —
   400,000              16.5                2.27
   800,000              39.7                2.40
 1,600,000              75.1                1.89

هر append به‌طورِ متوسط: 46.3 نانوثانیه
```

<div dir="rtl">

**ستونِ نسبت نزدیکِ `2` است.** ساعت و شمارنده یک چیز می‌گویند: **`n` بار `append` روی هم `O(n)` است.**

> 🔧 **اگر کار نکرد:** اگر خواستی همین اندازه‌گیری را روی یک `list` که **از قبل ساخته شده** انجام بدهی، تلهٔ فصلِ ۳ ترمِ ۱ برمی‌گردد — اندازه‌گیریِ گرم. این‌جا شکلِ دیگری دارد:

</div>

```python
shared = []
warm = 1000 * clock(lambda: shared.append(1), repeat=5)
print(f"زمانِ یک append روی ظرفِ مشترک: {warm:.6f} ms")
print(f"طولِ ظرف بعد از اندازه‌گیری   : {len(shared):,}")
```

```text-approx
زمانِ یک append روی ظرفِ مشترک: 0.000100 ms
طولِ ظرف بعد از اندازه‌گیری   : 6
```

<div dir="rtl">

**عددِ زمان بی‌معناست و سطرِ دوم دلیلش را لو می‌دهد:** `clock` شش بار تابع را صدا زد و هر بار یک عضو اضافه شد، پس اندازه‌گیری روی شش ظرفِ متفاوت انجام شده. **هر اندازه‌گیری باید ظرفِ تازهٔ خودش را داشته باشد** — همان قاعدهٔ «ورودیِ دست‌نخورده».

> 🤖 **از دستیارت بپرس:** «تفاوتِ هزینهٔ `amortised` و هزینهٔ بدترین حالت چیست؟» بعد این را هم بپرس: **«در چه نوع برنامه‌ای هزینهٔ `amortised` جوابِ درست نیست و باید بدترین تک‌عملیات را گزارش کرد؟»** — یکی از جواب‌های درست برنامه‌ای است که باید در یک مهلتِ ثابت جواب بدهد؛ آن‌جا یک `append` هزار برابری همان چیزی است که مهلت را می‌شکند، هرچقدر هم که میانگین خوب باشد.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| amortised cost | اِمورتایزد کاست | هزینهٔ کلِ یک دنبالهٔ عملیات، تقسیم بر تعدادشان |
| worst-case cost | ورست‌کیس کاست | گران‌ترین تکِ عملیاتِ ممکن |
| growth factor | گروث فکتور | عددی که ظرفیت هر بار در آن ضرب می‌شود |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: «`append` هزینهٔ `O(1)`ِ `amortised` دارد» دقیقاً چه چیزی را ادعا می‌کند و چه چیزی را نه؟

**تمرینِ اجباری:** `copied_constant` را با سه گامِ متفاوت اجرا کن: `step` برابرِ `128`، `1_024` و `8_192`. برای هر سه، جدولِ چهار اندازه‌ای بساز. **دو سؤال:** آیا بزرگ کردنِ گام ستونِ نسبت را از `4.00` پایین می‌آورد؟ و اگر نه، بزرگ کردنِ گام دقیقاً چه چیزی را بهتر می‌کند؟ جوابت باید بگوید تفاوتِ «ضریبِ ثابت» و «مرتبهٔ رشد» چیست.

**تمرینِ ستاره‌دار ⭐:** بخشِ ۲ را طوری تغییر بده که **هزینهٔ `amortised` را مستقیم رسم کند**: به‌ازای هر `k` از یک تا `N`، مجموعِ زمانِ `k` `append` اول تقسیم بر `k` را حساب کن و این دنباله را برای `k`های `1_000`، `10_000`، `100_000` و `400_000` چاپ کن. **قبل از اجرا پیش‌بینی کن این دنباله بالا می‌رود، پایین می‌آید یا صاف می‌ماند** و بنویس چرا. بعد اجرا کن. **اگر پیش‌بینی‌ات غلط بود، بنویس کدام یک از دو جدولِ بخشِ ۴ جوابِ درست را از قبل داشت.**

## در فصل بعد

سه فصل است داریم دربارهٔ **انتهای** ظرف حرف می‌زنیم: `append` در انتها، بزرگ‌شدن در انتها، خانهٔ خالی در انتها.

**فصلِ بعد به ابتدای ظرف نگاه می‌کند و همه‌چیز عوض می‌شود.** یک جدولِ دوبرابری برای `append` می‌گیریم و یکی برای `insert(0, x)`: ستونِ اولی نزدیکِ `2` است و دومی نزدیکِ `4`. بعد ظرفِ دیگری معرفی می‌شود که همان کارِ ابتدای ظرف را دوباره صاف می‌کند — و آن هم با جدول اثبات می‌شود، نه با ادعا.

</div>

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