# Big O چیست؟ پیچیدگی زمانی الگوریتم به زبان ساده، با اندازه‌گیری واقعی

`Big O` می‌گوید با بزرگ‌شدن داده، زمان اجرای یک الگوریتم با چه الگویی رشد می‌کند. `O(n)` یعنی اگر داده دو برابر شود، زمان هم حدود دو برابر می‌شود. `O(n²)` یعنی زمان حدود چهار برابر می‌شود. `Big O` زمان را به ثانیه نمی‌گوید. شکل رشد را می‌گوید.

## یک مسئله، دو راه

می‌خواهیم بدانیم در یک لیست عدد تکراری هست یا نه. راه اول هر عضو را با همهٔ عضوهای بعدش مقایسه می‌کند. راه دوم چیزهایی را که دیده در یک `set` نگه می‌دارد. این کد هر دو را اندازه می‌گیرد:

```python
import time

def has_duplicate_slow(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate_fast(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

def measure(fn, n):
    data = list(range(n))  # no duplicates: the worst case for both
    start = time.perf_counter()
    fn(data)
    return time.perf_counter() - start

for n in (2_000, 4_000, 8_000):
    print(n, round(measure(has_duplicate_slow, n), 4),
          round(measure(has_duplicate_fast, n), 6))
```

این عددها از یک اجرای واقعی به ثانیه آمده است. عدد روی دستگاه تو فرق می‌کند، ولی نسبت‌ها مهم‌اند:

| `n` | راه اول (`O(n²)`) | راه دوم (`O(n)`) |
|---|---|---|
| `2000` | `0.0545` | `0.000140` |
| `4000` | `0.2250` | `0.000207` |
| `8000` | `0.9088` | `0.000451` |

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

چرا چهار برابر؟ حلقهٔ تودرتو برای `n` عضو `n(n-1)/2` مقایسه انجام می‌دهد. برای `2000` عضو این عدد `1,999,000` است. اگر `n` دو برابر شود، تعداد مقایسه‌ها حدود چهار برابر می‌شود.

> **`Big O` پیش‌بینی است. داده را دو برابر کن، نسبت زمان‌ها را ببین و بسنج که پیش‌بینی درست بود یا نه.**

## پیچیدگی‌های رایج

| نماد | وقتی `n` دو برابر شود | مثال |
|---|---|---|
| `O(1)` | تقریباً تغییری نمی‌کند | خواندن یک عضو لیست با اندیس |
| `O(log n)` | یک قدم اضافه | جست‌وجوی دودویی در لیست مرتب |
| `O(n)` | حدود دو برابر | پیمایش لیست |
| `O(n log n)` | کمی بیشتر از دو برابر | مرتب‌سازی با `sorted` |
| `O(n²)` | حدود چهار برابر | حلقهٔ تودرتو روی همان داده |

برای حس اندازه، به تعداد قدم‌ها برای یک میلیون داده نگاه کن:

| | `n = 1,000,000` |
|---|---|
| `log₂ n` | حدود `20` |
| `n` | `1,000,000` |
| `n log₂ n` | حدود `20,000,000` |
| `n²` | `1,000,000,000,000` |

## `Big O` را از روی کد چطور بخوانیم

سه قاعدهٔ کاری کافی است:

1. **حلقه‌های پشت‌سرهم جمع می‌شوند.** دو حلقهٔ جدا روی `n` عضو می‌شود `2n`، یعنی `O(n)`.
2. **حلقه‌های تودرتو ضرب می‌شوند.** حلقه در حلقه روی همان داده می‌شود `O(n²)`.
3. **ثابت‌ها و جمله‌های کوچک حذف می‌شوند.** `3n² + 5n` همان `O(n²)` است، چون در `n` بزرگ جملهٔ غالب تعیین‌کننده است.

## دامی که در پایتون پنهان است

یک خط کوتاه می‌تواند خودش یک حلقه باشد:

```python
x in my_list  # scans the list: O(n)
x in my_set   # hash lookup: O(1) on average
```

روی همان دستگاه و با یک میلیون عضو، جست‌وجوی عضو آخر در `list` حدود `9` میلی‌ثانیه طول کشید و در `set` کمتر از یک‌هزارم میلی‌ثانیه. اگر این خط داخل یک حلقه باشد، کل کار بی‌صدا `O(n²)` می‌شود. برای همین راه دوم ما سریع است: `x in seen` روی `set` است، نه `list`.

عبارت «به‌طور میانگین» هم مهم است. `set` در بدترین حالت می‌تواند کندتر شود، و `O(1)` قول میانگین است.

## چیزی که `Big O` نمی‌گوید

**ثابت پنهان را نمی‌گوید.** الگوریتم `O(n)` با ثابت بزرگ ممکن است برای داده‌های کوچک از `O(n²)` با ثابت کوچک کندتر باشد. اگر داده‌ات همیشه ده تاست، الگوریتم ساده شاید بهترین انتخاب باشد.

**حافظه را نمی‌گوید.** راه دوم ما سریع‌تر است، ولی برای `set` حافظهٔ اضافه مصرف می‌کند. پیچیدگی حافظه را جدا می‌سنجند.

**خودش نمی‌گوید کدام حالت است.** `Big O` یک کران بالاست و باید بگویی دربارهٔ کدام حالت حرف می‌زنی. راه اول اگر تکراری را زود پیدا کند، زود تمام می‌شود، و برای همین در اندازه‌گیری داده‌ای بدون تکرار ساختیم.

## جمع‌بندی

برای هر کد کند، اول اندازه بگیر. داده را دو برابر کن و نسبت زمان را ببین. اگر حدود چهار برابر شد، دنبال حلقهٔ تودرتو یا `in` روی `list` بگرد. خودآموز [بنیاد](/courses/bonyad) با همین قاعده جلو می‌رود: هیچ ادعای پیچیدگی بدون جدول اندازه‌گیری. [خودآموز دانلودی بنیاد](/store/bonyad-book) نسخهٔ دانلودی همان دوره است.

---
Source: https://yaadestan.com/blog/big-o-explained (یادستان, Yaadestan)
