نماد Big-O با کد واقعی

کد شما روی ۱۰۰ آیتم کار می‌کند. آیا روی ۱٬۰۰۰٬۰۰۰ آیتم هم کار خواهد کرد؟ نماد Big-O به همین سؤال جواب می‌دهد. این نماد توصیف می‌کند که زمان اجرا (یا مصرف حافظهٔ) یک الگوریتم با بزرگ‌تر شدن ورودی چطور رشد می‌کند.

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

ایدهٔ اصلی: رشد، نه سرعت#

Big-O نمی‌گوید یک تابع ۳ میلی‌ثانیه طول می‌کشد. می‌گوید زمان چطور مقیاس می‌پذیرد:

• اگر ورودیِ یک تابع O(n) را دو برابر کنید، زمان تقریباً دو برابر می‌شود.
• اگر ورودیِ یک تابع O(n²) را دو برابر کنید، زمان تقریباً چهار برابر می‌شود.

ثابت‌ها و جمله‌های کوچک‌تر را هم کنار می‌گذاریم. تابعی که 3n + 10 گام برمی‌دارد همان O(n) است، چون وقتی n بزرگ می‌شود، 3 و 10 در مقایسه با خودِ رشد اهمیتی ندارند.

O(1): زمان ثابت#

مقدار کار اصلاً به اندازهٔ ورودی بستگی ندارد:

def get_first(items):
    return items[0]

def is_even(n):
    return n % 2 == 0

دسترسی به یک خانهٔ لیست، جست‌وجوی یک کلید در دیکشنری و افزودن به انتهای لیست (به‌طور میانگین) همه O(1) هستند.

O(n): زمان خطی#

مقدار کار به نسبت مستقیم با ورودی رشد می‌کند. یک بار پیمایش همهٔ آیتم‌ها مثال کلاسیک آن است:

def find_max(numbers):
    largest = numbers[0]
    for n in numbers:          # runs n times
        if n > largest:
            largest = n
    return largest

عملیات O(n)ِ پنهان را هم خوب است بشناسید: x in some_list، some_list.index(x)، sum() و max() همه کل لیست را پیمایش می‌کنند.

O(n²): زمان درجهٔ دو#

حلقه‌ای داخل حلقهٔ دیگر که هر دو روی ورودی اجرا می‌شوند، تقریباً n × n گام به شما می‌دهد:

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

برای ۱٬۰۰۰ آیتم این حدود نیم میلیون مقایسه است. برای ۱٬۰۰۰٬۰۰۰ آیتم حدود ۵۰۰ میلیارد. این فاصلهٔ بین «فوری» و «فردا برگرد» است.

راه‌حل: حافظه را با سرعت معاوضه کنید#

می‌توانیم has_duplicates را با به خاطر سپردنِ آیتم‌های دیده‌شده در یک set به O(n) برسانیم؛ بررسی عضویت در set به‌طور میانگین O(1) است:

def has_duplicates(items):
    seen = set()
    for item in items:          # runs n times
        if item in seen:        # O(1) on average
            return True
        seen.add(item)          # O(1) on average
    return False

یا به شکل خلاصه‌تر:

def has_duplicates(items):
    return len(set(items)) != len(items)

کمی حافظهٔ اضافه (فضای O(n)) خرج می‌کنیم تا مقدار عظیمی زمان صرفه‌جویی کنیم. این معاوضه یکی از رایج‌ترین بهینه‌سازی‌ها در کدهای دنیای واقعی است.

O(log n): زمان لگاریتمی#

الگوریتم‌های لگاریتمی در هر گام مسئله را نصف می‌کنند. جست‌وجوی دودویی (binary search) روی یک لیست مرتب، مثال درسیِ آن است:

def binary_search(sorted_items, target):
    low, high = 0, len(sorted_items) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            return mid
        if sorted_items[mid] < target:
            low = mid + 1       # discard the left half
        else:
            high = mid - 1      # discard the right half
    return -1

جست‌وجو در ۱٬۰۰۰٬۰۰۰ آیتم مرتب حداکثر حدود ۲۰ گام طول می‌کشد، چون ۲ به توان ۲۰ تقریباً ۱٬۰۰۰٬۰۰۰ است. داده را دو برابر کنید و فقط یک گام اضافه می‌شود.

O(n log n): نقطهٔ طلایی مرتب‌سازی#

الگوریتم‌های مرتب‌سازیِ کارآمد و همه‌منظوره در O(n log n) اجرا می‌شوند؛ از جمله merge sort و Timsort که پشتوانهٔ sorted() و list.sort() در پایتون است. این فقط کمی بدتر از خطی است و بهترین حالت ممکن برای مرتب‌سازی از طریق مقایسهٔ عناصر است.

names = sorted(names)   # O(n log n)

مقایسهٔ نرخ‌های رشد#

تعداد تقریبی گام‌ها برای اندازه‌های مختلف ورودی:

چطور کد خودتان را تحلیل کنید#

1. حلقه‌ها را پیدا کنید. حلقه‌ای روی ورودی معمولاً O(n) است. حلقه‌های تودرتو روی ورودی در هم ضرب می‌شوند: O(n²).
2. داخل فراخوانی توابع را ببینید. item in my_list داخل یک حلقه، یک حلقهٔ تودرتوی پنهان است.
3. بزرگ‌ترین جمله را نگه دارید. O(n² + n) ساده می‌شود به O(n²).
4. به بدترین حالت فکر کنید. اگر چیز دیگری گفته نشده باشد، Big-O معمولاً بدترین حالت را توصیف می‌کند.

یک مثال فریبنده. پیچیدگی‌اش چقدر است؟

def common_items(a, b):
    return [x for x in a if x in b]

اگر b یک لیست باشد، x in b هر بار آن را پیمایش می‌کند، پس این کد O(n × m) است. اول b را به set تبدیل کنید تا به O(n + m) برسد:

def common_items(a, b):
    b_set = set(b)                          # O(m)
    return [x for x in a if x in b_set]     # O(n)

جمع‌بندی#

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

دفعهٔ بعد که کدتان با بزرگ شدن داده کند شد، اول سراغ سرور سریع‌تر نروید. سراغ Big-O بروید.