BÀI 1: ĐỘ PHỨC TẠP THUẬT TOÁN

Dành cho đội tuyển HSG Tin học - THPT Phan Chu Trinh

1. Khái niệm về "Thước đo sức mạnh" $O$

Trong lập trình thi đấu, không phải cứ ra kết quả đúng là có điểm. Bạn phải ra kết quả đúng trong thời gian cho phép (thường là 1 giây).

Quy tắc vàng: Máy tính xử lý được khoảng 10⁷ - 10⁸ phép tính mỗi giây. Nếu thuật toán của bạn vượt quá con số này, bạn sẽ nhận lỗi TLE (Time Limit Exceeded).

2. Ví dụ: Tính tổng từ 1 đến $N$

Đề bài: Tính tổng $S = 1 + 2 + 3 + \dots + n$ với $n$ là số nguyên dương nhập từ bàn phím.
CÁCH 1: Duyệt tuần tự (Vòng lặp for - Duyệt vòng lặp $O(N)$) Mô tả: Giống như việc em đi bộ từ cổng trường vào lớp, bước đủ $n$ bước, mỗi bước cộng thêm 1 giá trị vào tổng.Mã nguồn Python:

def sum_linear(n):
    s = 0
     for i in range(1, n + 1):
         s += i
     return s

=> Càng nhiều bước ($N$ lớn), máy càng tốn thời gian.

Phân tích:
    - Kiến thức: Sử dụng biến tích lũy và vòng lặp cơ bản.
    -Tư duy: Tuyến tính (Linear). $n$ tăng gấp đôi thì máy phải làm việc gấp đôi.
    - Độ phức tạp: $O(n)$.).

CÁCH 2: Dùng công thức toán học (Gauss)

Mô tả: Thay vì đi bộ, em dùng "siêu năng lực" dịch chuyển tức thời. Chỉ cần một phép tính duy nhất là ra kết quả.:

def sum_constant(n):
    return n * (n + 1) // 2

=> Dù $N$ lớn bao nhiêu, chỉ cần 1 bước tính là xong!

Phân tích:
    - Kiến thức: Áp dụng công thức tổng cấp số cộng: $$S = \frac{n(n+1)}{2}$$
    -Tư duy: TTối ưu (Constant). Không phụ thuộc vào độ lớn của $n$.
    - Độ phức tạp: $O(1)$

🔬 PHÒNG THÍ NGHIỆM THUẬT TOÁN

import time
def demo_complexity(n):
    print(f"\n--- Thử nghiệm với n = {n:,} ---")
    # Đo Cách 1: O(n)
    start = time.time()
    res1 = sum_linear(n)
    end = time.time()
     print(f"Cách 1 (Vòng lặp): Kết quả = {res1}, Thời gian = {end - start:.5f} giây")
    # Đo Cách 2: O(1)
    start = time.time()
    res2 = sum_constant(n)
    end = time.time()
     print(f"Cách 2 (Toán học): Kết quả = {res2}, Thời gian = {end - start:.5f} giây")
# Chạy thử nghiệm
demo_complexity(10**7) # 10 triệu
demo_complexity(10**8) # 100 triệu

Nhập số $N$ để so sánh tốc độ (Thử với $N = 10,000,000$):

Cách 2 - $O(1)$: ---

Cách 1 - $O(N)$: ---

3. Bài học rút ra

• Tư duy tuần tự: Dễ nhưng chậm.
• Tư duy tối ưu: Cần kiến thức nhưng cực nhanh.