`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 تا.

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

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

قبل از شروع#

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

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

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

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

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

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

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

🌱 ریشه‌اش کجاست: f(n) در این نماد دقیقاً همان تابع است: ماشینی که n می‌گیرد و یک عدد بیرون می‌دهد. اگر این تصویر برایت تازه است، ریشه ترمِ ۴ فصل ۱ از صفر می‌سازدش — و بعدش O(n²) فقط یک نامِ کوتاه برای «آن ماشینی که خروجی‌اش با مربعِ ورودی می‌رود» است.

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

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

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

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}%")

       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%

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

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

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

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

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

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()

— اندازه‌های کوچک
         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

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² نسبتِ پایدارِ بالای چهار نمی‌دهد.

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

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

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}")

         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

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

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

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

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}")

one_pass     :    0.17 ms
three_passes :    0.57 ms
نسبت         :    3.24

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

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

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

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])

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

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

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

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

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

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

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

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

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

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

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

ZeroDivisionError: division by zero

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

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

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

در فصل بعد#

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

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