در این فصل چه یاد میگیری#
تقریباً هر کدی که در عمرت بنویسی یا بخوانی، یکی از شش شکلِ رشد را دارد. این فصل هر ششتا را با شمارنده میسازد، نامِ رسمیشان را میگذارد، و بعد یک سؤال از همهشان میپرسد: اگر n هزار برابر شود، کار چند برابر میشود؟
جوابها اینها هستند: 1، 2، 1,000، 2,000، 1,001,000 — و برای ششمی، عددی با 300,729 رقم.
آن سطرِ آخر شوخی نیست و توضیحش این است که چرا بعضی مسئلهها با هیچ کامپیوترِ سریعتری حل نمیشوند.
آخر این فصل میتوانی:
- شش مرتبهٔ اصلیِ رشد را با نامِ
O(...)بشناسی و نمونهٔ کدِ هرکدام را بنویسی - از روی ستونِ نسبت بگویی یک کد کدام شکل را دارد
- شمارشِ عملیات را به زمانِ تخمینی روی ماشینِ خودت تبدیل کنی
- بگویی چرا
O(2^n)را نمیشود با سختافزارِ بهتر نجات داد
قبل از شروع#
از فصلِ ۵: جدولِ دوبرابری و قاعدهٔ خواندنِ ستونِ نسبت. این فصل روی همان قاعده اسم میگذارد.
از فصلِ ۴: شمارندهٔ عملیات.
نمادِ O(...) را از این فصل بهکار میبریم، ولی تعریفِ دقیقش فصلِ بعد است. فعلاً همینقدر بدان که O(n²) یعنی «کار با مربعِ n میرود»؛ فصلِ ۷ میگوید این جمله دقیقاً چه چیزی را ادعا میکند و چه چیزی را نمیکند.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. پنج منحنیِ اول، با شمارنده#
پنج تابعِ کوچک مینویسیم که هرکدام یک شکلِ رشدِ متفاوت دارند، و همهشان را روی یک نردبانِ دوبرابری میبریم.
🤔 اول حدس بزن: برای
O(n log n)بنویس ستونِ نسبت چه عددی میدهد. بین2و4است یا بیرونِ این بازه؟ و آیا با بزرگ شدنِnبالا میرود یا پایین؟
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))
شمارشِ عملیات
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
جدولِ دوم همان قاعدهٔ فصلِ ۵ است، این بار با اسم:
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)را چک کن.
۲. منحنیِ ششم#
پنج منحنیِ بالا همه راماند. ششمی نیست.
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))))
n عملیات نسبت به سطر قبل
2 4 —
4 16 4.00
8 256 16.00
16 65,536 256.00
فرمول برای n = 20: 1048576 · شمارشِ واقعی: 1048576
به ستونِ نسبت نگاه کن: 4، بعد 16، بعد 256. خودِ نسبت هم منفجر میشود.
در پنج منحنیِ قبل، ستونِ نسبت به عددی میرسید و آنجا میماند. در O(2^n) ستونِ نسبت هر بار مربع میشود. برای همین این تنها مرتبهای است که با هیچ ماشینی نمیشود نجاتش داد: ماشینِ هزار برابر سریعتر، فقط ده واحد به nی که میتوانی حل کنی اضافه میکند — چون 2¹⁰ حدودِ هزار است.
آخرین سطر هم مهم است: شمارشِ واقعی با فرمولِ 2^n مو نمیزند. فرمول را حدس نزدیم؛ راستیآزماییاش کردیم — و از این به بعد هر جا فرمولی مینویسیم، همین کار را میکنیم.
🌱 ریشهاش کجاست: اینکه چرا
2^nاینقدر زود از کنترل خارج میشود و چرا شهودِ آدم همیشه کمبرآوردش میکند، در ریشه ترمِ ۴ فصل ۷ با مثالِ ملموس ساخته شده. وlogکه در سه منحنیِ دیگر ظاهر شد، دقیقاً وارونهٔ همین است — ریشه ترمِ ۴ فصل ۸.
۳. از شمارش تا زمان#
شمارش مستقل از ماشین است، ولی گاهی میخواهی بدانی این کار روی ماشینِ خودت چقدر طول میکشد. برای این کار یک عدد لازم داری: ماشینِ تو در ثانیه چند عملِ ساده انجام میدهد؟ آن را اندازه میگیریم و بقیه یک تقسیم است.
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}")
سرعتِ اندازهگیریشدهٔ این ماشین: 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 سال
در n = 10 هر شش مرتبه در چند میکروثانیه تمام میشوند و انتخاب بینشان بیمعناست. در n = 100 یکیشان از عمرِ جهان بیشتر طول میکشد.
⚠️ مواظب باش: این جدول حساب شده است، نه اندازهگیریشده — بهجز عددِ سرعتِ ماشین که واقعاً گرفته شد. ما
O(2^n)را درn = 1000اجرا نکردیم؛ شمارشش را از فرمول برداشتیم و تقسیم بر سرعت کردیم. جدولی که برونیابی است باید خودش این را بگوید، وگرنه خواننده آن را بهجای مشاهده میگیرد. یک ایرادِ صادقانهٔ دیگر هم دارد: «عمل» در همهٔ این مرتبهها هزینهٔ یکسانی ندارد و ما فرض کردیم دارد. فصلِ ۹ نشان میدهد این فرض کجا میشکند.
۴. اگر n هزار برابر شود#
سؤالی که در کارِ واقعی بیشتر از همه پرسیده میشود این نیست که «الان چقدر طول میکشد»؛ این است که «اگر دادهام ده یا صد یا هزار برابر شود، چه بلایی سرم میآید».
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}")
مرتبه کار چند برابر میشود؟
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 رقم
این جدول را حفظ کن؛ بیشتر از هر جدولِ دیگری در این دوره بهکارت میآید.
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) دیده میشود.
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.")
شش منحنی روی محورِ عمودیِ لگاریتمی رسم شدند؛ n از 1 تا 32.
دو چیز در این نمودار مهم است.
اول اینکه در nهای کوچکِ سمتِ چپ، منحنیها به هم چسبیدهاند و حتی جایشان عوض میشود. تمامِ فصلِ ۹ دربارهٔ همان ناحیه است.
دوم اینکه O(2^n) روی محورِ لگاریتمی یک خطِ راست است. این خودش تعریفِ رشدِ نمایی است: روی محورِ لگاریتمی صاف میشود، چون در هر قدم در یک عددِ ثابت ضرب میشود.
🔧 اگر کار نکرد: اگر
nرا در جدولِ بخشِ ۳ خیلی بزرگ بگیری، پایتون سرِ تقسیم میایستد:
try:
print(2 ** 2_000 / RATE)
except OverflowError as err:
print(f"{type(err).__name__}: {err}")
OverflowError: int too large to convert to float
پیام دقیقاً همان درسِ این فصل را میدهد: عددِ صحیحِ پایتون سقف ندارد و 2 ** 2000 را بیدردسر میسازد، ولی عددِ اعشاری سقف دارد و آن عدد در آن جا نمیشود. راهِ درست این است که بهجای خودِ عدد، تعدادِ رقمهایش را حساب کنی — دقیقاً کاری که در بخشِ ۴ با math.log10 کردیم.
🤖 از دستیارت بپرس: «چرا
O(n log n)فقط دو برابرِO(n)بدتر است وقتیnهزار برابر میشود؟» بعد این را هم بپرس: «اگر کامپیوترم هزار برابر سریعتر شود، برای هر یک از این شش مرتبه، بزرگترینnی که در یک ثانیه حل میکنم چند برابر میشود؟» — جوابِO(n)هزار برابر است، جوابِO(n²)حدودِ سیودو برابر، و جوابِO(2^n)فقط ده واحد بیشتر. همین سه عدد کلِ درسِ این فصلاند.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
O(1) |
اُ یک | هزینه به اندازهٔ ورودی کاری ندارد |
O(log n) |
اُ لگ اِن | هر دو برابر شدنِ n فقط یک قدم اضافه میکند |
O(n) |
اُ اِن | یک بار دیدنِ همهٔ داده |
O(n log n) |
اُ اِن لگ اِن | چند بار دیدنِ همهٔ داده، به تعدادِ نصفشدنها |
O(n²) |
اُ اِن دو | هر عضو با هر عضو |
O(2^n) |
اُ دو به توانِ اِن | همهٔ حالتهای ممکن؛ عملاً غیرقابلِ اجرا |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
حالا شش اسم داریم و هنوز تعریفِ دقیقی نداریم. فصلِ بعد Big-O را تعریف میکند و سه چیز را با عدد نشان میدهد: چرا فقط جملهٔ غالب میماند، چرا ثابتها حذف میشوند، و چه چیزی را Big-O عمداً به تو نمیگوید.
آزمایشِ اصلیاش یک تابع با سه جمله است — 3n² + 100n + 5000. در n = 10 سهمِ جملهٔ n² از کلِ کار زیرِ پنج درصد است؛ در n = 10,000 بالای ۹۹ درصد. همان دو عدد کلِ دلیلِ وجودِ Big-O را میسازند.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.