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 107 - 108 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
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)$.).
- 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
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)$
- 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
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.
📌 Danh sách bình luận