Big O Notation: آنچه A-Level CS واقعاً انتظار دارد

Big O notation در هر spec A-level علوم کامپیوتر اصلی (AQA, OCR, Edexcel) ظاهر می‌شود و بسیاری از دانش‌آموزان را سردرگم می‌کند نه برای اینکه ریاضیات سخت است، بلکه برای اینکه هرگز آن را به کد واقعی متصل نمی‌بینند. این یک راهنمای عملی در مورد آنچه باید بدانید و نحوه پاسخ به سؤالات امتحانی آن بدون پرلاف است.

Big O واقعاً چه را اندازه می‌گیرد

Big O نحوه رشد زمان اجرا (یا استفاده از حافظه) یک الگوریتم را با رشد اندازه ورودی، معمولاً n نامیده می‌شود، توصیف می‌کند. این یک اندازه‌گیری کرونومتر در ثانیه نیست. این روشی است برای توصیف نرخ رشد تا بتوانید الگوریتم‌ها را صرف‌نظر از سخت‌افزار مقایسه کنید.

وقتی O(n) را می‌نویسید، می‌گویید: اگر ورودی را دو برابر کنم، کار تقریباً دو برابر می‌شود. O(n²) به معنای دو برابر کردن ورودی، کار را تقریباً چهار برابر می‌کند. این رابطه همان چیزی است که ممتحنان می‌خواهند شما شناسایی کنید، نه شمارش دقیق عملیات.

پیچیدگی‌هایی که باید خوب یاد بگیرید

برای A-level، اینها آن‌هایی هستند که بارها و بارها ظاهر می‌شوند:

• O(1) – زمان ثابت. دسترسی به عنصر آرایه براساس شاخص: arr[5]. فرقی نمی‌کند آرایه چقدر بزرگ است.
• O(log n) – لگاریتمی. جستجوی دودویی در لیست مرتب شده. هر مرحله فضای جستجوی باقی‌مانده را نصف می‌کند.
• O(n) – خطی. یک حلقه واحد از طریق لیست، مثل جستجوی خطی که هر آیتم را یک بار بررسی می‌کند.
• O(n log n) – خطی‌لگاریتمی. Merge sort و quicksort (موارد متوسط) اینجا قرار می‌گیرند.
• O(n²) – درجه دوم. حلقه‌های تو در تو روی داده‌های یکسان، که دقیقاً کاری است که bubble sort، insertion sort و selection sort انجام می‌دهند.
• O(2ⁿ) – نمایی. Fibonacci بازگشتی ساده بدون memoisation. خیلی سریع بدتر می‌شود.

باید بتوانید به pseudocode نگاه کنید و بگویید در لحظه کدام یک است، زیرا تقریباً این همان چیزی است که آزمایش می‌شود.

خواندن کد برای پیچیدگی

روشی که هر بار کار می‌کند: حلقه‌ها را بشمارید و ببینید چگونه با n ارتباط دارند.

# O(n) - یک حلقه، یک پاس
for i in range(n):
    print(i)

# O(n^2) - حلقه تو در تو، هر دو به n مرتبط
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - فضای جستجو در هر تکرار نصف می‌شود
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

حلقه تو در تو که دامنه حلقه داخلی به n بستگی دارد هنوز O(n²) است، حتی اگر کمی متفاوت به نظر برسد (مثل for j in range(i) به جای for j in range(n) — هنوز هم درجه دوم است، فقط با تفاوت ضریب ثابتی).

حلقه‌هایی را که به n بستگی ندارند احتیاط کنید. حلقه‌ای که صرف‌نظر از اندازه ورودی همیشه 10 بار اجرا می‌شود O(1) است، حتی اگر حلقه وجود داشته باشد. ممتحنان دوست دارند این را مخفی کنند.

الگوریتم‌های مرتب‌سازی متداول و Big O آنها

این یک موضوع امتحانی مورد علاقه است زیرا دو spec را ترکیب می‌کند: الگوریتم‌های مرتب‌سازی و پیچیدگی.

Algorithm	Best case	Worst case
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

سازگاری Merge sort (پیچیدگی یکسان بهترین و بدترین حالت) شایسته یادآوری صریح است اگر سؤالی بپرسد چرا آن را به جای bubble sort برای مجموعه‌های بزرگ انتخاب می‌کنید. بهترین حالت bubble sort O(n) تنها زمانی اعمال می‌شود که بهینه‌سازی خروج زودهنگام وجود داشته باشد زمانی که هیچ تعویضی در یک پاس اتفاق نیفتد — آن جزئیات را ذکر کنید اگر آن را مطرح کنید، زیرا برخی از هیئت‌های امتحانی آن را انتظار می‌برند.

جایی که دانش‌آموزان نمره از دست می‌دهند

بزرگ‌ترین یک: نوشتن