Big O Notation: What A-Level CS Actually Expects

Big O notation xuất hiện trên mọi spec A-level computer science chính (AQA, OCR, Edexcel) và nó làm khó dễ rất nhiều học sinh không phải vì toán học khó, mà vì họ không bao giờ thấy nó liên kết với code thực tế. Đây là một hướng dẫn thực tế về những gì bạn cần biết và cách trả lời các câu hỏi thi mà không tắc miễng.

Big O thực sự đo lường gì

Big O mô tả cách thời gian chạy (hoặc sử dụng bộ nhớ) của một thuật toán tăng khi kích thước đầu vào, thường được gọi là n, trở nên lớn hơn. Nó không phải là phép đo bằng đồng hồ bấm giây tính bằng giây. Nó là cách mô tả tốc độ tăng trưởng để bạn có thể so sánh các thuật toán độc lập với phần cứng.

Khi bạn viết O(n), bạn đang nói: nếu tôi nhân đôi đầu vào, công việc sẽ tăng gấp đôi. O(n²) có nghĩa là nhân đôi đầu vào sẽ làm công việc tăng gấp bốn lần. Mối quan hệ đó là cái mà người chấm thi muốn bạn xác định, chứ không phải đếm các phép toán chính xác.

Các độ phức tạp bạn cần nắm vững

Đối với A-level, đây là những cái xuất hiện lại và lại:

• O(1) – thời gian hằng số. Truy cập phần tử mảng theo chỉ mục: arr[5]. Không quan trọng mảng lớn như thế nào.
• O(log n) – logarit. Binary search trên danh sách được sắp xếp. Mỗi bước giảm một nửa không gian tìm kiếm còn lại.
• O(n) – tuyến tính. Một vòng lặp duy nhất qua danh sách, giống như linear search kiểm tra từng mục một lần.
• O(n log n) – tuyến tính logarit. Merge sort và quicksort (trường hợp trung bình) nằm ở đây.
• O(n²) – bậc hai. Các vòng lặp lồng nhau qua cùng một dữ liệu, chính xác là những gì bubble sort, insertion sort và selection sort làm.
• O(2ⁿ) – mũ. Fibonacci recursive ngây thơ mà không memoisation. Trở nên tồi tệ nhanh chóng.

Bạn nên có thể nhìn vào pseudocode và nói đó là cái nào trong những cái này một cách tức thì, vì đó chủ yếu là những gì được kiểm tra.

Đọc code để xác định độ phức tạp

Phương pháp hoạt động mọi lúc: đếm các vòng lặp và xem chúng liên quan với n như thế nào.

# O(n) - một vòng lặp, một lần duyệt
for i in range(n):
    print(i)

# O(n^2) - vòng lặp lồng nhau, cả hai liên kết với n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - không gian tìm kiếm giảm một nửa mỗi lần lặp
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

Một vòng lặp lồng nhau mà phạm vi của vòng lặp bên trong phụ thuộc vào n vẫn là O(n²), ngay cả khi nó trông hơi khác (như for j in range(i) thay vì for j in range(n) — đó vẫn là bậc hai tổng thể, chỉ với sự khác biệt hệ số hằng số).

Cẩn thận với các vòng lặp không phụ thuộc vào n chút nào. Một vòng lặp luôn chạy 10 lần bất kể kích thước đầu vào là O(1), ngay cả khi có vòng lặp. Người chấm thi thích đặt điều này vào.

Các thuật toán sắp xếp phổ biến và Big O của chúng

Đây là chủ đề thi yêu thích vì nó kết hợp hai spec cùng lúc: các thuật toán sắp xếp và độ phức tạp.

Thuật toán	Trường hợp tốt nhất	Trường hợp tồi nhất
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)

Tính nhất quán của merge sort (cùng độ phức tạp trường hợp tốt nhất và tồi nhất) đáng để đề cập rõ ràng nếu một câu hỏi hỏi tại sao bạn lại chọn nó thay vì bubble sort cho các tập dữ liệu lớn. Trường hợp tốt nhất O(n) của bubble sort chỉ áp dụng với tối ưu hóa thoát sớm khi không có hoán đổi xảy ra trong một lần duyệt — hãy đề cập chi tiết đó nếu bạn nêu lên, vì một số hội đồng thi kỳ vọng nó.

Những nơi học sinh mất điểm

Cái lớn nhất: viết