پیچیدگی الگوریتم و نماد Big-O

الگوریتم شما درست کار می‌کند؛ اما «درست» تنها معیار نیست. یک کار را می‌شود با ده الگوریتم مختلف انجام داد که یکی در یک ثانیه تمام می‌شود و دیگری با دادهٔ بزرگ، عملاً هیچ‌وقت. برای این‌که دربارهٔ «خوب بودن» به‌جای احساس، با عدد صحبت کنیم، به یک زبان مشترک نیاز داریم: نماد Big-O.

ثانیه نشمارید، گام بشمارید

اگر زمان اجرا را با ساعت‌سنجی بگیرید، نتیجه به کامپیوتر، زبان برنامه‌نویسی و حتی فشار شبکه بستگی دارد؛ فردا روی دستگاه دیگر عوض می‌شود. چیزی که به این جزئیات وابسته نیست، «تعداد گام‌های پایه» است: هر مقایسه، هر جمع و هر جابه‌جایی یک گام است.

مقدار این تعداد به اندازهٔ ورودی بستگی دارد؛ برای ورودی با n عنصر، تعداد گام‌ها تابعی از n است و به همین تابع می‌گوییم «پیچیدگی» (Complexity) الگوریتم.

نماد Big-O

نماد Big-O رفتار تابع پیچیدگی را وقتی n بزرگ می‌شود توصیف می‌کند: در برابر ضریب‌ها و جمله‌های کوچکِ اثرناپذیر کور است و فقط سرعت رشد را نگه می‌دارد. یعنی اگر الگوریتمی ۳n + ۵ گام ببرد، می‌گوییم O(n) است؛ چون وقتی n میلیون‌ها باشد، تنها جملهٔ مسلط n است و ضرایب تفاوت ماهوی نمی‌سازند. این قرارداد دقیقاً همان چیزی است که برای مقایسهٔ مقیاس‌پذیری لازم داریم. پیاده‌سازی رسمی و دقیق این نماد را در ارجاع پایان درس می‌بینید؛ در عمل با این خانواده‌ها سروکار دارید:

برای حس کردن تفاوت، جدول این رشدها را برای چند n ببینید:

وقتی n ده برابر می‌شود، الگوریتم خطی ده برابر کار می‌کند، الگوریتم درجه دو صد برابر، و الگوریتم لگاریتمی فقط چند گام اضافه. همین تفاوت است که یک قابلیت را ممکن یا ناممکن می‌کند.

جست‌وجوی خطی در برابر دودویی

فرض کنید عددی را در فهرست مرتب‌شدهٔ یک‌میلیونی از اعداد می‌جوییم. «جست‌وجوی خطی» همان الگوریتم درس قبل است: از اول شروع کن و تا پیدا شدن برو. «جست‌وجوی دودویی» (Binary Search) وسط را نگاه می‌کند؛ اگر عدد هدف بزرگ‌تر بود، نیمهٔ اول را برای همیشه دور می‌ریزد و با نیمهٔ دوم همین کار را تکرار می‌کند. در هر گام، نصف فضای جست‌وجو از بین می‌رود.

هر دو الگوریتم فقط «تعداد گام» خود را برمی‌گردانند تا بتوانیم آن‌ها را مستقیم مقایسه کنیم:

def linear_search_steps(data, target):
    steps = 0
    for value in data:
        steps += 1
        if value == target:
            return steps
    return steps

def binary_search_steps(data, target):
    low, high = 0, len(data) - 1
    steps = 0
    while low <= high:
        mid = (low + high) // 2
        steps += 1
        if data[mid] == target:
            return steps
        if data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return steps

data = list(range(1, 1000001))
print("Linear search:", linear_search_steps(data, 999999))
print("Binary search:", binary_search_steps(data, 999999))

باور نمی‌کنید؟ برای پیدا کردن ۹۹۹٬۹۹۹ در یک میلیون عدد، جست‌وجوی خطی ۹۹۹٬۹۹۹ مقایسه کرد؛ دودویی فقط ۱۹. اگر ورودی را ده برابر کنید، خطی تا ده میلیون مقایسه می‌رود (O(n)) و دودویی شاید به ۲۳ می‌رسد (O(log n)). رشد لگاریتمی یعنی هر ۲۰ گام اضافه، تقریباً یک میلیون برابر فضای جدید.

خط‌به‌خط بخش دودویی:

1. low و high مرزهای ناحیهٔ جست‌وجو هستند؛ ابتدا کل فهرست.
2. mid = (low + high) // 2 عنصر میانی را می‌گیرد؛ // تقسیم صحیح است.
3. اگر مقدار میانی خودِ هدف بود، تمام. اگر کوچک‌تر بود هدف در نیمهٔ راست است، پس low را جلو می‌بریم؛ وگرنه high را عقب.

تشخیص سریع پیچیدگی

نیازی به شمارش دقیق نیست؛ دو علامت روشن دارد:

• حلقهٔ سادهٔ روی n عنصر — معمولاً O(n). دو حلقهٔ «پشت‌سرهم» هنوز O(n) است؛ ضریب ۲ را دور می‌ریزیم.
• حلقهٔ تودرتو — حلقه‌ای داخل حلقه، هر دو روی n: معمولاً O(n²). چون برای هر یک از n عنصر بیرونی، n کار داخلی انجام می‌شود.

n = 5
steps = 0
for i in range(n):
    for j in range(n):
        steps += 1
print(steps)

n=۵، تعداد گام‌ها ۲۵؛ رابطهٔ n² عیناً در خروجی دیده می‌شود. در تمرین‌ها این را برای nهای دیگر آزمایش می‌کنید.

تمرین‌ها

# Write your code here

for n in [1, 10, 20]:
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1
    print(n, steps)

تعداد گام‌ها همیشه دقیقاً n² است چون حلقهٔ داخلی به‌طور کامل برای هر عنصر حلقهٔ بیرونی اجرا می‌شود؛ رفتار درجه دو، هم آزمایشی و هم نظری تأیید شد. ::: :::

# Write your code here

n = 16
steps = 0
i = 1
while i <= n:
    steps += 1
    i = i * 2
print(steps)

گام‌ها ۱ و ۲ و ۴ و ۸ و ۱۶ هستند؛ پنج گام برای n=۱۶. تعداد گام‌ها حدوداً log₂ n است، پس این رفتار از خانوادهٔ O(log n) است — همان منطق جست‌وجوی دودویی. ::: :::

خلاصه

• هزینهٔ الگوریتم را با تعداد گام‌های پایه می‌سنجیم، نه با زمان اجرای روی سخت‌افزار خاص.
• Big-O فقط سرعت رشد را نگه می‌دارد: ضریب‌ها و جمله‌های کوچک حذف می‌شوند.
• خانواده‌های اصلی: O(1) ثابت، O(log n) لگاریتمی، O(n) خطی، O(n log n) خطی‌لگاریتمی و O(n²) درجه دو.
• جست‌وجوی دودویی با O(log n) در هر گام نصف فضا را دور می‌ریزد و همین آن را بر خطی برتری می‌دهد.

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