تصویر شاخص نوشته: Big O چیست؟ پیچیدگی زمانی الگوریتم به زبان ساده، با اندازه‌گیری واقعی

Big O چیست؟ پیچیدگی زمانی الگوریتم به زبان ساده، با اندازه‌گیری واقعی

۱۳ آبان ۱۴۰۵ مبانی برنامه‌نویسی

Big O می‌گوید با بزرگ‌شدن داده، زمان اجرای یک الگوریتم با چه الگویی رشد می‌کند. O(n) یعنی اگر داده دو برابر شود، زمان هم حدود دو برابر می‌شود. O(n²) یعنی زمان حدود چهار برابر می‌شود. Big O زمان را به ثانیه نمی‌گوید. شکل رشد را می‌گوید.

یک مسئله، دو راه

می‌خواهیم بدانیم در یک لیست عدد تکراری هست یا نه. راه اول هر عضو را با همهٔ عضوهای بعدش مقایسه می‌کند. راه دوم چیزهایی را که دیده در یک set نگه می‌دارد. این کد هر دو را اندازه می‌گیرد:

import time

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

def has_duplicate_fast(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

def measure(fn, n):
    data = list(range(n))  # no duplicates: the worst case for both
    start = time.perf_counter()
    fn(data)
    return time.perf_counter() - start

for n in (2_000, 4_000, 8_000):
    print(n, round(measure(has_duplicate_slow, n), 4),
          round(measure(has_duplicate_fast, n), 6))

این عددها از یک اجرای واقعی به ثانیه آمده است. عدد روی دستگاه تو فرق می‌کند، ولی نسبت‌ها مهم‌اند:

n راه اول (O(n²)) راه دوم (O(n))
2000 0.0545 0.000140
4000 0.2250 0.000207
8000 0.9088 0.000451

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

چرا چهار برابر؟ حلقهٔ تودرتو برای n عضو n(n-1)/2 مقایسه انجام می‌دهد. برای 2000 عضو این عدد 1,999,000 است. اگر n دو برابر شود، تعداد مقایسه‌ها حدود چهار برابر می‌شود.

Big O پیش‌بینی است. داده را دو برابر کن، نسبت زمان‌ها را ببین و بسنج که پیش‌بینی درست بود یا نه.

پیچیدگی‌های رایج

نماد وقتی n دو برابر شود مثال
O(1) تقریباً تغییری نمی‌کند خواندن یک عضو لیست با اندیس
O(log n) یک قدم اضافه جست‌وجوی دودویی در لیست مرتب
O(n) حدود دو برابر پیمایش لیست
O(n log n) کمی بیشتر از دو برابر مرتب‌سازی با sorted
O(n²) حدود چهار برابر حلقهٔ تودرتو روی همان داده

برای حس اندازه، به تعداد قدم‌ها برای یک میلیون داده نگاه کن:

n = 1,000,000
log₂ n حدود 20
n 1,000,000
n log₂ n حدود 20,000,000
n² 1,000,000,000,000

Big O را از روی کد چطور بخوانیم

سه قاعدهٔ کاری کافی است:

  1. حلقه‌های پشت‌سرهم جمع می‌شوند. دو حلقهٔ جدا روی n عضو می‌شود 2n، یعنی O(n).
  2. حلقه‌های تودرتو ضرب می‌شوند. حلقه در حلقه روی همان داده می‌شود O(n²).
  3. ثابت‌ها و جمله‌های کوچک حذف می‌شوند. 3n² + 5n همان O(n²) است، چون در n بزرگ جملهٔ غالب تعیین‌کننده است.

دامی که در پایتون پنهان است

یک خط کوتاه می‌تواند خودش یک حلقه باشد:

x in my_list  # scans the list: O(n)
x in my_set   # hash lookup: O(1) on average

روی همان دستگاه و با یک میلیون عضو، جست‌وجوی عضو آخر در list حدود 9 میلی‌ثانیه طول کشید و در set کمتر از یک‌هزارم میلی‌ثانیه. اگر این خط داخل یک حلقه باشد، کل کار بی‌صدا O(n²) می‌شود. برای همین راه دوم ما سریع است: x in seen روی set است، نه list.

عبارت «به‌طور میانگین» هم مهم است. set در بدترین حالت می‌تواند کندتر شود، و O(1) قول میانگین است.

چیزی که Big O نمی‌گوید

ثابت پنهان را نمی‌گوید. الگوریتم O(n) با ثابت بزرگ ممکن است برای داده‌های کوچک از O(n²) با ثابت کوچک کندتر باشد. اگر داده‌ات همیشه ده تاست، الگوریتم ساده شاید بهترین انتخاب باشد.

حافظه را نمی‌گوید. راه دوم ما سریع‌تر است، ولی برای set حافظهٔ اضافه مصرف می‌کند. پیچیدگی حافظه را جدا می‌سنجند.

خودش نمی‌گوید کدام حالت است. Big O یک کران بالاست و باید بگویی دربارهٔ کدام حالت حرف می‌زنی. راه اول اگر تکراری را زود پیدا کند، زود تمام می‌شود، و برای همین در اندازه‌گیری داده‌ای بدون تکرار ساختیم.

جمع‌بندی

برای هر کد کند، اول اندازه بگیر. داده را دو برابر کن و نسبت زمان را ببین. اگر حدود چهار برابر شد، دنبال حلقهٔ تودرتو یا in روی list بگرد. خودآموز بنیاد با همین قاعده جلو می‌رود: هیچ ادعای پیچیدگی بدون جدول اندازه‌گیری. خودآموز دانلودی بنیاد نسخهٔ دانلودی همان دوره است.

اگر می‌خواهی این موضوع را کامل یاد بگیری

خودآموز بنیاد

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

ساختمان داده و الگوریتم را با پایتون یاد بگیر، با اندازه‌گیری به‌جای حفظ‌کردن. کدت درست کار می‌کند و روی دادهٔ واقعی غیرقابلِ استفاده است. این دوره می‌گوید چرا — و مهم‌تر، چطور قبل از اجرا پیش‌بینی‌اش کنی: اندازه‌گیریِ صادقانهٔ زمان، Big-O به‌عنوان یک پیش‌بینی که آزمون می‌دهد، list و hash و درخت و گراف، مرتب‌سازی و جست‌وجو، و یک قاعدهٔ سخت — هیچ ادعای پیچیدگی بدونِ جدولِ اندازه‌گیری. همه در Google Colab، فقط روی CPU و فقط با کتابخانهٔ استاندارد.

  • ۶ ترم
  • ۴۹ فصل
  • همهٔ فصل‌ها رایگان

برای خواندن بدون اینترنت

خودآموز دانلودی بنیاد

PDF، EPUB، MOBI · ۸۲۴ صفحه

۲۹۹٬۰۰۰ تومان

دیدن نسخهٔ دانلودی