در این فصل چه یاد میگیری#
سه فصل الگوریتم نوشتیم و هیچکدام از n log n جلوتر نرفت. این فصل نشان میدهد چرا هیچوقت نمیرود — و استدلالش هیچ ربطی به الگوریتم ندارد؛ فقط شمردن است.
بعد عددش را میگیریم: در n = 8,000 کمترین تعدادِ مقایسهٔ ممکن 92,193 است و merge sort ما 93,704 میکند. نسبتِ 1.02 — یعنی الگوریتمی که خودمان نوشتیم، دو درصد با مرزِ نظری فاصله دارد.
و آخرش الگوریتمی میآوریم که از این مرز رد میشود، چون اصلاً مقایسه نمیکند. اندازه میگیریم که کجا برنده است — ۷۱ برابر سریعتر از merge sort ما — و کجا ۱۹۷ برابر بازنده.

آخر این فصل میتوانی:
- بگویی چرا
n!ترتیبِ ممکن، مرزی برای تعدادِ مقایسهها میسازد - فاصلهٔ الگوریتمِ خودت با آن مرز را حساب کنی
counting sortرا بنویسی و بگویی چه شرطی دارد- با عدد بگویی آن شرط کِی بهصرفه است و کِی فاجعه
قبل از شروع#
از فصلِ ۴: merge sort و شمارشِ مقایسههایش — کدش اینجا دوباره، فشرده، میآید تا فصل خودبسنده باشد.
از ترمِ ۱ فصلِ ۶: خانوادهٔ منحنیهای رشد، و مخصوصاً اینکه log n چقدر کند بالا میرود.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. چند جوابِ ممکن وجود دارد؟#
مرتب کردن یعنی پیدا کردنِ یک ترتیبِ خاص از بینِ همهٔ ترتیبهای ممکن. پس اولین سؤال این است: چند ترتیب ممکن است؟
import math
from itertools import permutations
for n in (3, 4, 5, 10, 20):
print(f"n = {n:>2} ترتیبهای ممکن = {math.factorial(n):,}")
print("\nهمهٔ ترتیبهای سه عضو:")
for p in permutations("abc"):
print(" ", "".join(p))
n = 3 ترتیبهای ممکن = 6
n = 4 ترتیبهای ممکن = 24
n = 5 ترتیبهای ممکن = 120
n = 10 ترتیبهای ممکن = 3,628,800
n = 20 ترتیبهای ممکن = 2,432,902,008,176,640,000
همهٔ ترتیبهای سه عضو:
abc
acb
bac
bca
cab
cba
برای سه عضو شش ترتیب، و برای بیست عضو عددی با نوزده رقم. الگوریتمِ مرتبسازی باید بتواند بگوید ورودی کدامیک از اینها بوده.
🌱 ریشهاش کجاست: «چند جور میشود
nچیز را پشتِ سرِ هم چید» همان جایگشت است و در ریشه ترمِ ۶ فصل ۱ با اصلِ ضرب ساخته میشود: برای جای اولnانتخاب داری، برای جای دومn-1تا، و همینطور تا آخر. حاصلضربشان میشودn!— و همان فصل نشان میدهد این عدد چقدر زود از هر عددِ آشنایی بزرگتر میشود.
۲. هر مقایسه چه چیزی به تو میدهد#
حالا سؤالِ دوم: یک مقایسه چقدر از این ابهام را کم میکند؟
جوابش «کمی» نیست، یک عددِ دقیق است. هر مقایسه دو جوابِ ممکن دارد — بله یا نه. پس بعد از k مقایسه، حداکثر 2^k مسیرِ متفاوت طی کردهای، و هر مسیر فقط میتواند به یک ترتیب ختم شود.
پس برای اینکه الگوریتم بتواند هر n! ترتیب را از هم تشخیص بدهد، باید 2^k دستِکم به n! برسد.
print(f"{'مقایسه':>8}{'حالتِ قابلِ تفکیک (2^k)':>26}{'برای ۳ عضو کافی است؟':>24}")
for k in range(1, 4):
print(f"{k:>8}{2 ** k:>26,}{str(2 ** k >= math.factorial(3)):>24}")
مقایسه حالتِ قابلِ تفکیک (2^k) برای ۳ عضو کافی است؟
1 2 False
2 4 False
3 8 True
با دو مقایسه فقط چهار حالت را میشود از هم جدا کرد و ما شش حالت داریم. پس هیچ الگوریتمِ مقایسهای — هیچکدام، هرچقدر هم زیرک — نمیتواند سه عضو را همیشه با دو مقایسه مرتب کند. این حرف دربارهٔ یک الگوریتمِ خاص نیست؛ دربارهٔ همهٔ الگوریتمهای ممکن است، حتی آنهایی که هنوز نوشته نشدهاند.
همین شرط را برای n بزرگ مینویسیم: از 2^k ≥ n! نتیجه میشود که k دستِکم log₂(n!) است.
def log2_factorial(n):
"""log2(n!) بدونِ ساختنِ خودِ n! — جمعِ لگاریتمها."""
return sum(math.log2(i) for i in range(2, n + 1))
for n in (10, 100, 1_000):
print(f"n = {n:>5} مرزِ پایین = {math.ceil(log2_factorial(n)):>7,} مقایسه"
f" · n × log2(n) = {n * math.log2(n):>9,.0f}")
n = 10 مرزِ پایین = 22 مقایسه · n × log2(n) = 33
n = 100 مرزِ پایین = 525 مقایسه · n × log2(n) = 664
n = 1000 مرزِ پایین = 8,530 مقایسه · n × log2(n) = 9,966
ستونِ دوم و سوم همیشه در همان حدودِ هم میمانند — نسبتشان از 0.66 به 0.86 میرود و به یک نزدیکتر میشود. یعنی log₂(n!) و n log₂ n از یک خانوادهاند و همان O(n log n) را میگویند. پس مرزِ پایینِ مرتبسازیِ مقایسهای از مرتبهٔ n log n است، و این را با شمردن ثابت کردیم، نه با اندازهگیری.
۳. الگوریتمِ ما چقدر با مرز فاصله دارد؟#
مرزِ پایین میگوید «کمتر از این ممکن نیست». ولی نمیگوید کسی به آن میرسد. حالا اندازه میگیریم.
🤔 اول حدس بزن: بهنظرت
merge sortچند برابرِ مرزِ پایین مقایسه میکند؟ یک عدد بنویس — دو برابر؟ ده برابر؟ — بعد جدول را ببین.
def merge_sort(values):
"""merge sort فصلِ ۴، فشرده، با شمارشِ مقایسه."""
comparisons = 0
def go(vals):
nonlocal comparisons
if len(vals) <= 1:
return vals
mid = len(vals) // 2
left, right = go(vals[:mid]), go(vals[mid:])
out = []
i = j = 0
while i < len(left) and j < len(right):
comparisons += 1
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
return go(list(values)), comparisons
rng = random.Random(SEED)
LADDER = [1_000, 2_000, 4_000, 8_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in LADDER}
print("merge sort درست کار میکند؟",
merge_sort(shuffled[1_000])[0] == sorted(shuffled[1_000]))
print()
print(f"{'n':>8}{'مرزِ پایین':>14}{'merge sort':>14}{'نسبت':>10}")
for n in LADDER:
floor_ = math.ceil(log2_factorial(n))
got = merge_sort(shuffled[n])[1]
print(f"{n:>8,}{floor_:>14,}{got:>14,}{got / floor_:>10.2f}")
merge sort درست کار میکند؟ True
n مرزِ پایین merge sort نسبت
1,000 8,530 8,709 1.02
2,000 19,053 19,415 1.02
4,000 42,100 42,781 1.02
8,000 92,193 93,704 1.02
1.02 در هر چهار سطر. یعنی merge sort — الگوریتمی که خودمان در یک فصل نوشتیم — دو درصد با بهترین چیزی که نظریه اجازه میدهد فاصله دارد، و این فاصله با بزرگتر شدنِ n باز نمیشود.
این جدول دو خبر دارد. خبرِ خوب اینکه merge sort تقریباً بهینه است. خبرِ مهمتر اینکه دنبالِ الگوریتمِ مقایسهایِ بهتر گشتن، اتلافِ وقت است — حتی یک الگوریتمِ کامل و بینقص هم فقط دو درصد بهتر میشود.
و همینجا یک بدهیِ ترمِ ۱ پرداخت میشود. فصلِ ۷ آن ترم Θ و Ω را در چند خط تعریف کرد و از آن به بعد هیچجا بهکار نرفتند — چون تا امروز فقط سقف داشتیم. این تنها جای کلِ دوره است که هر دو نصفه را با هم در دست داری: فصلِ ۴ سقفِ merge sort را داد (O(n log n)، با جدول) و بخشِ ۲ کفِ هر الگوریتمِ مقایسهای را (Ω(n log n)، با شمردن). وقتی سقف و کف یکی باشند، دیگر میشود Θ نوشت: مرتبسازیِ مقایسهای Θ(n log n) است، و ستونِ 1.02 نشان میدهد که این فقط یک ادعای نمادین نیست — فاصلهٔ سقف و کف روی دادههای واقعیِ ما دو درصد است.
پس اگر میخواهی واقعاً سریعتر شوی، باید از بازیِ مقایسه بیرون بروی.
۴. الگوریتمی که هیچ دو عضوی را با هم مقایسه نمیکند#
فرض کن میدانی همهٔ عضوها عددِ صحیحِ بینِ 0 و k-1 هستند. آنوقت لازم نیست بپرسی کدام بزرگتر است؛ فقط باید بشماری هر عدد چند بار آمده.
def counting_sort(values, k):
"""بدونِ حتی یک مقایسه بینِ دو عضو. شرط: هر عضو عددِ صحیحِ ۰ تا k-1."""
counts = [0] * k
for v in values:
counts[v] += 1 # فقط شمردن، نه مقایسه
out = []
for value in range(k):
out.extend([value] * counts[value])
return out
small = [5, 2, 9, 2, 0, 5, 5]
print("ورودی :", small)
print("خروجی :", counting_sort(small, 10))
print("با sorted یکی است؟", counting_sort(small, 10) == sorted(small))
ورودی : [5, 2, 9, 2, 0, 5, 5]
خروجی : [0, 2, 2, 5, 5, 5, 9]
با sorted یکی است؟ True
در این کد هیچجا دو عضوِ ورودی با هم مقایسه نمیشوند. ترتیب از آدرس درمیآید، نه از مقایسه — دقیقاً همان ایدهای که ترمِ ۲ فصلِ ۱ برای دسترسیِ آرایه ساخت.
پس مرزِ پایینِ بخشِ ۲ به این الگوریتم اصلاً مربوط نیست. آن استدلال دربارهٔ الگوریتمهایی بود که تنها ابزارشان مقایسه است. مرز باطل نشد؛ این الگوریتم از قلمروش بیرون است.
هزینهاش را میشماریم: n بار شمردن، k بار پیمودنِ خانهها، و n بار نوشتن.
🤔 اول حدس بزن: با ثابت ماندنِ
kو دو برابر شدنِn، ستونِ نسبت چه میشود؟ و با ثابت ماندنِnو دو برابر شدنِkچه؟ دو عدد بنویس.
def counting_steps(values, k):
"""گامهای واقعیِ counting sort — شمرده، نه حسابشده."""
counts = [0] * k
steps = 0
for v in values:
counts[v] += 1
steps += 1
for value in range(k):
steps += 1 + counts[value]
return steps
K_SMALL = 256
COUNT_LADDER = [25_000, 50_000, 100_000, 200_000]
bytes_ = {n: [rng.randrange(K_SMALL) for _ in range(n)] for n in COUNT_LADDER}
print("جواب با sorted یکی است؟",
counting_sort(bytes_[25_000], K_SMALL) == sorted(bytes_[25_000]))
print("\n— گامها، با k ثابت روی ۲۵۶")
table([(n, counting_steps(bytes_[n], K_SMALL)) for n in COUNT_LADDER], "گام", ",d")
جواب با sorted یکی است؟ True
— گامها، با k ثابت روی ۲۵۶
n گام نسبت به سطر قبل
25,000 50,256 —
50,000 100,256 1.99
100,000 200,256 2.00
200,000 400,256 2.00
FIXED = bytes_[100_000]
print("— گامها، با n ثابت روی ۱۰۰٬۰۰۰ و k دو برابر شونده")
print(f"{'k':>12}{'گام':>14}{'نسبت به سطر قبل':>20}")
previous = None
for k in (200_000, 400_000, 800_000, 1_600_000):
steps = counting_steps(FIXED, k)
ratio = "—" if not previous else f"{steps / previous:.2f}"
print(f"{k:>12,}{steps:>14,}{ratio:>20}")
previous = steps
— گامها، با n ثابت روی ۱۰۰٬۰۰۰ و k دو برابر شونده
k گام نسبت به سطر قبل
200,000 400,000 —
400,000 600,000 1.50
800,000 1,000,000 1.67
1,600,000 1,800,000 1.80
جدولِ اول 2.00 میدهد — با k ثابت، counting sort خطی است. هیچ logی در کار نیست.
جدولِ دوم چیزِ مهمتری میگوید: با ثابت ماندنِ n، بالا بردنِ k هم کار را زیاد میکند، و نسبتش رفتهرفته به 2 نزدیکتر میشود — یعنی هرچه k بزرگتر شود، k بخشِ غالبِ هزینه میشود و n دیگر تعیینکننده نیست. هزینه O(n + k) است و هیچکدام از این دو حرف را نمیشود انداخت.
۵. حالا هر دو طرفِ معامله را اندازه بگیر#
big = [rng.randrange(K_SMALL) for _ in range(100_000)]
print("هر سه یک جواب میدهند؟",
counting_sort(big, K_SMALL) == sorted(big) == merge_sort(big)[0])
mine = clock(lambda: merge_sort(big), repeat=2)
counting = clock(lambda: counting_sort(big, K_SMALL), repeat=3)
builtin = clock(lambda: sorted(big), repeat=3)
print(f"\nn = 100,000 · k = 256")
print(f" merge sortِ ما (پایتونِ خالص): {1000 * mine:>8,.1f} ms")
print(f" counting sort (پایتونِ خالص) : {1000 * counting:>8,.1f} ms")
print(f" sorted (نوشتهشده به C) : {1000 * builtin:>8,.1f} ms")
print(f"\n counting در برابرِ merge sortِ ما: {mine / counting:>5,.1f} برابر سریعتر")
print(f" counting در برابرِ sorted : {builtin / counting:>5,.1f} برابر سریعتر")
هر سه یک جواب میدهند؟ True
n = 100,000 · k = 256
merge sortِ ما (پایتونِ خالص): 281.0 ms
counting sort (پایتونِ خالص) : 3.9 ms
sorted (نوشتهشده به C) : 8.9 ms
counting در برابرِ merge sortِ ما: 71.6 برابر سریعتر
counting در برابرِ sorted : 2.3 برابر سریعتر
در مقایسهٔ منصفانه — دو الگوریتم، هر دو در پایتونِ خالص — counting sort حدودِ هفتاد برابر جلوتر است. این نتیجهٔ عوض شدنِ مرتبه است: O(n + k) در برابرِ O(n log n).
ولی نسبتِ دومی فقط 2.3 است، و همین عدد صادقانهترین سطرِ این فصل است: الگوریتمی با مرتبهٔ بهتر، در برابرِ sorted که مرتبهاش بدتر است، فقط دو برابر جلو میافتد — چون sorted به زبانِ C نوشته شده و ثابتش دهها برابر کوچکتر است. این همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹ است و فصلِ ۸ کاملاً بازش میکند.
حالا شرط را بشکن: همان n، ولی بازهٔ مقادیر خیلی بازتر.
K_WIDE = 5_000_000
wide = [rng.randrange(K_WIDE) for _ in range(20_000)]
print("جواب با sorted یکی است؟", counting_sort(wide, K_WIDE) == sorted(wide))
slow = clock(lambda: counting_sort(wide, K_WIDE), repeat=2)
ref = clock(lambda: sorted(wide), repeat=3)
print(f"\nn = 20,000 · k = 5,000,000")
print(f" counting sort: {1000 * slow:>8,.1f} ms")
print(f" sorted : {1000 * ref:>8,.1f} ms")
print(f" نسبت : {slow / ref:>8,.0f} برابر بهنفعِ sorted")
print(f" حافظهٔ آرایهٔ شمارش: {sys.getsizeof([0] * K_WIDE) / 1024 / 1024:,.1f} مگابایت")
جواب با sorted یکی است؟ True
n = 20,000 · k = 5,000,000
counting sort: 516.4 ms
sorted : 2.6 ms
نسبت : 197 برابر بهنفعِ sorted
حافظهٔ آرایهٔ شمارش: 38.1 مگابایت
همان الگوریتم، همان جوابِ درست، و این بار ۱۹۷ برابر بازنده — چون برای بیست هزار عدد، پنج میلیون خانه ساخت و همهشان را پیمود. و حافظهاش هم از دادهای که مرتب میکند خیلی بزرگتر شد.
⚠️ مواظب باش: بزرگ کردنِ
kدر Colab خطرِ واقعی دارد. اگرK_WIDEرا چند برابر کنی، ممکن است بهجایMemoryError، نشست بدونِ هیچ پیامی ریاستارت شود و هر چیزی که در حافظه داشتی از دست برود. قبل از ساختنِ آرایهٔ شمارش، حجمش را با یک ضرب حساب کن — همان عددی که سطرِ آخرِ خروجیِ بالا چاپ میکند.
۶. وقتی شرط برقرار نیست#
try:
counting_sort([3, 1, 2], 2)
except IndexError as err:
print(f"{type(err).__name__}: {err}")
try:
counting_sort([1.5, 0.5], 3)
except TypeError as err:
print(f"{type(err).__name__}: {err}")
IndexError: list index out of range
TypeError: list indices must be integers or slices, not float
🔧 اگر کار نکرد: دو پیام، دو شکستِ شرط.
IndexErrorیعنی عضوی بزرگتر یا مساویِkدر داده بوده —kرا از خودِ داده حساب کن (max(values) + 1)، نه از حدس.TypeErrorیعنی عضوها عددِ صحیح نیستند؛counting sortروی اعشار اصلاً معنا ندارد، چون بینِ هر دو عددِ اعشاری بینهایت عددِ دیگر هست و «خانهٔ شمارهدار» بیمعنا میشود.هر دو خطا خبرِ خوبیاند. بدترین حالت این بود که کد بیصدا جوابِ غلط بدهد.
✅ چک کن:
kرا از داده حساب کن —counting_sort(values, max(values) + 1)— و روی[5, 2, 9, 2, 0, 5, 5]امتحانش کن. باید همان[0, 2, 2, 5, 5, 5, 9]را بدهد. حالا عددِ9را به900000تغییر بده و قبل از اجرا حساب کن آرایهٔ شمارش چند خانه میشود. اگر جوابت را نوشتی، فهمیدهای چراkبخشی از صورتِ مسئله است، نه یک جزئیاتِ پیادهسازی.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ مرزِ پایینِ شمارشی با مقایسههای واقعیِ
merge sort؛ و بعدcounting sortباmerge sortو باsorted، هر سه با جوابِ تأییدشدهٔ برابر. در کدام بازهٔn؟ ۱٬۰۰۰ تا ۸٬۰۰۰ برای جدولِ مرز، ۲۵٬۰۰۰ تا ۲۰۰٬۰۰۰ برای گامهایcounting sort، و دو مقایسهٔ زمانی درn = 100,000باk = 256و درn = 20,000باk = 5,000,000. با چند تکرار، و کمینه یا میانگین؟ جدولهای شمارش یک اجرا و قطعی؛ مقایسههای زمانی دو تا سه تکرار بهعلاوهٔ گرمکننده، کمینه، و هر سه روی همان داده.
🤖 از دستیارت بپرس: «چرا
counting sortمرزِ پایینِn log nرا نقض نمیکند؟» بعد این را هم بپرس: «اگر بخواهم یک میلیون عددِ صحیحِ بینِ صفر و یک میلیارد را مرتب کنم،counting sortانتخابِ خوبی است؟» — جوابِ درست باید حافظهٔ آرایهٔ شمارش را حساب کند و بگوید نه. اگر دستیارت فقط گفت «counting sortخطی است پس بهتر است»، خروجیِ آخرِ بخشِ ۵ را جلویش بگذار.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| lower bound | لوئر باوند | کمترین کاری که هیچ الگوریتمی از آن پایینتر نمیرود |
| comparison sort | کامپریزن سورت | مرتبسازیای که تنها ابزارش پرسیدنِ «کدام بزرگتر است؟» است |
counting sort |
کانتینگ سورت | مرتبسازی با شمردنِ تکرارِ هر مقدار، بدونِ هیچ مقایسهای |
| permutation | پرمیوتیشن | یکی از ترتیبهای ممکنِ یک مجموعه |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
این فصل گفت مرتب کردن گران است — n log n، و کمتر از آن ممکن نیست. پس ارزشش را دارد؟
فصلِ بعد نشان میدهد داشتنِ یک فهرستِ مرتب چه چیزی میخرد: پرسشِ «هست یا نه؟» که با جستوجوی خطی در n = 8,000 حدودِ ۴٬۰۰۰ گام میخواست، با ۱۳ گام جواب میگیرد. و بعد نقطهٔ سربهسرش را حساب میکنیم: از q = 24 پرسش به بعد، مرتب کردن بهصرفه است.
و همانجا بدترین ردهٔ خطا را هم میبینیم: نسخهای از binary search که هیچ خطایی نمیدهد و برای ۴۸۹ عضو از ۱٬۰۰۰ عضوِ موجود میگوید «پیدا نشد».
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.