Phân tích Vòng lặp & Cấu trúc Điều kiện

Quy tắc 1: Vòng lặp đơn và bước nhảy (Step size)

• Vòng lặp tăng/giảm theo phép cộng: i += 1 hoặc i -= 1 $\rightarrow$ Chạy $N$ lần $\rightarrow O(N)$.

• Vòng lặp tăng/giảm theo phép nhân/chia: i *= 2 hoặc i //= 2 $\rightarrow$ Số bước chạy là $\log_2 N \rightarrow O(\log N)$.

Quy tắc 2: Câu lệnh điều kiện if - else

Thời gian thực thi của cấu trúc if - else được tính bằng thời gian của điều kiện cộng với nhánh tốn thời gian nhất:

2. Phân tích Thuật toán Đệ quy (Recursion Analysis)

Khi một hàm tự gọi lại chính nó, ta biểu diễn thời gian thực thi dưới dạng Phương trình truy hồi (Recurrence Relation).

Ví dụ 1: Đệ quy tính Giai thừa (Factorial)

def factorial(n):
    if n <= 1:
        return 1  # O(1)
    return n * factorial(n - 1)  # T(n - 1) + O(1)

• Phương trình truy hồi: $T(n) = T(n - 1) + O(1)$

• Khai triển:

  $$T(n) = T(n - 1) + 1 = T(n - 2) + 1 + 1 = \dots = T(1) + (n - 1) = O(n)$$

• Độ phức tạp bộ nhớ (Space Complexity): $O(n)$ do hệ thống phải lưu $n$ khung hàm (stack frames) trên Call Stack.

Ví dụ 2: Đệ quy Chia để trị (Binary Search)

• Phương trình truy hồi: $T(n) = T\left(\frac{n}{2}\right) + O(1)$ (chia đôi bài toán và tốn $O(1)$ để so sánh).

• Khai triển:

  $$T(n) = T\left(\frac{n}{2}\right) + 1 = T\left(\frac{n}{4}\right) + 2 = \dots = T(1) + \log_2 n = O(\log n)$$

3. Mã nguồn Minh họa Phân tích Độ phức tạp các dạng Cấu trúc

# 1. Vòng lặp biến thiên gián tiếp: O(log N)
def loop_logarithmic(n):
    i = 1
    count = 0
    while i < n:
        count += 1
        i = i * 2  # i nhân đôi sau mỗi bước: 1, 2, 4, 8, 16...
    return count


# 2. Vòng lặp lồng phụ thuộc (Dependent Nested Loop): O(N^2)
def loop_dependent(n):
    total = 0
    for i in range(n):
        # Vòng j chạy từ 0 đến i (chạy 1, 2, 3... n lần)
        for j in range(i):
            total += 1
    # Tổng số lần chạy: 1 + 2 + 3 + ... + (n-1) = n*(n-1)/2 -> O(N^2)
    return total


# 3. Đệ quy nhị phân (Binary Recursion) - Fibonacci thuần túy: O(2^N)
def fibonacci(n):
    if n <= 1:
        return n
    # Gọi 2 nhánh đệ quy độc lập -> Cây đệ quy nhị phân độ sâu N
    return fibonacci(n - 1) + fibonacci(n - 2)

BÀI TẬP CỦNG CỐ 

Bài tập 1: Phân tích Cây Đệ quy & Độ phức tạp

Cho đoạn mã đệ quy sau:

def mystery_function(n):
    if n <= 1:
        return 1
    print("Processing...")
    mystery_function(n // 2)
    mystery_function(n // 2)

1. Lập phương trình truy hồi $T(n)$ cho hàm trên.

2. Xác định độ phức tạp thời gian $O(?)$ và độ phức tạp bộ nhớ $O(?)$ (Call Stack).

Bài tập 2: Tối ưu hóa Bài toán Đệ quy

Hàm fibonacci(n) thuần túy ở ví dụ trên có độ phức tạp $O(2^n)$ do tính lại các nhánh trùng lặp.

1. Hãy vẽ sơ đồ thể hiện sự trùng lặp khi tính fibonacci(5).

2. Viết lại hàm fibonacci_memo(n, memo={}) ứng dụng kỹ thuật Ghi nhớ (Memoization) để hạ độ phức tạp thời gian xuống còn $O(N)$.