Dãy Fibonacci là một trong những dãy số nổi tiếng nhất trong toán học và khoa học máy tính, được định nghĩa bởi quy tắc đơn giản: mỗi số là tổng của hai số đứng trước nó. Với các giá trị khởi đầu thường là F₀ = 0, F₁ = 1, dãy số tiếp tục như 0, 1, 1, 2, 3, 5, 8, 13, .... Mặc dù định nghĩa rất đơn giản, có nhiều cách tiếp cận khác nhau để tính toán các số Fibonacci, mỗi cách có ưu nhược điểm riêng về hiệu suất và độ phức tạp.

1. Phương pháp Đệ quy Trực tiếp

Cách đơn giản nhất để triển khai dãy Fibonacci là sử dụng định nghĩa đệ quy trực tiếp: F(n) = F(n-1) + F(n-2). Điều kiện dừng thường là F(1) = 1 và F(2) = 1 (hoặc F(0)=0, F(1)=1 tùy theo quy ước).

long long fibonacciRecursive(int k) {
    if (k <= 0) {
        return 0; // Hoặc xử lý lỗi cho input không hợp lệ
    }
    if (k == 1 || k == 2) {
        return 1;
    }
    // Gọi đệ quy cho hai phần tử trước đó
    return fibonacciRecursive(k - 1) + fibonacciRecursive(k - 2);
}

Độ phức tạp: Phương pháp này có độ phức tạp thời gian là O(2ⁿ) do các phép tính lặp lại. Độ phức tạp không gian là O(n) do chiều sâu của stack đệ quy.

2. Quy hoạch động với Mảng (Bộ nhớ O(n))

Để khắc phục nhược điểm của phương pháp đệ quy trực tiếp là tính toán đi tính toán lại các giá trị đã biết, chúng ta có thể sử dụng quy hoạch động (Dynamic Programming). Phương pháp này tính toán các giá trị từ dưới lên và lưu trữ chúng trong một mảng để tái sử dụng.

#include <vector> // Cần thiết cho std::vector

long long fibonacciDynamicArray(int k) {
    if (k <= 0) return 0;
    if (k == 1 || k == 2) return 1;

    // Sử dụng std::vector để lưu trữ các giá trị đã tính toán
    std::vector<long long> dp(k + 1);
    dp[1] = 1;
    dp[2] = 1;

    for (int i = 3; i <= k; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[k];
}

Độ phức tạp: Độ phức tạp thời gian là O(n) vì mỗi số Fibonacci được tính một lần. Độ phức tạp không gian là O(n) để lưu trữ mảng.

3. Phương pháp Lặp với cửa sổ Vector (Bộ nhớ O(1))

Chúng ta có thể tối ưu hóa phương pháp quy hoạch động về không gian bằng cách chỉ lưu trữ hai giá trị Fibonacci gần nhất, thay vì toàn bộ dãy. Điều này có thể được thực hiện bằng cách sử dụng một std::vector kích thước cố định.

#include <vector> // Cần thiết cho std::vector

long long fibonacciVectorWindow(int k) {
    if (k <= 0) return 0;
    if (k == 1 || k == 2) return 1;

    // Lưu trữ hai giá trị Fibonacci gần nhất: {F(i-1), F(i-2)}
    std::vector<long long> current_pair = {1, 1}; 

    for (int i = 3; i <= k; ++i) {
        long long next_fib = current_pair[0] + current_pair[1];
        current_pair[1] = current_pair[0]; // F(i-2) trở thành F(i-1) cũ
        current_pair[0] = next_fib;        // F(i-1) trở thành F(i) mới
    }
    return current_pair[0]; // Giá trị F(k)
}

Độ phức tạp: Độ phức tạp thời gian là O(n), nhưng độ phức tạp không gian được giảm xuống O(1) vì chỉ sử dụng một số lượng cố định các biến (hoặc phần tử trong vector).

4. Sử dụng Hàng đợi (std::queue)

Tương tự như phương pháp tối ưu không gian, một hàng đợi (queue) có thể được sử dụng để duy trì hai số Fibonacci cuối cùng cần thiết cho việc tính toán số tiếp theo. Khi một số Fibonacci mới được tính, số cũ nhất không còn cần thiết sẽ được loại bỏ khỏi hàng đợi.

#include <queue> // Cần thiết cho std::queue

long long fibonacciQueue(int k) {
    if (k <= 0) return 0;
    if (k == 1 || k == 2) return 1;

    std::queue<long long> fib_q;
    fib_q.push(1); // F(1)
    fib_q.push(1); // F(2)

    for (int i = 3; i <= k; ++i) {
        long long next_val = fib_q.front() + fib_q.back(); // Tính F(i) = F(i-2) + F(i-1)
        fib_q.pop();                                     // Loại bỏ F(i-2)
        fib_q.push(next_val);                            // Thêm F(i) vào hàng đợi
    }
    return fib_q.back(); // Trả về F(k)
}

Độ phức tạp: Độ phức tạp thời gian là O(n) và độ phức tạp không gian là O(1).

5. Phương pháp Lặp Tối ưu (Chỉ với vài biến)

Đây là phương pháp lặp hiệu quả nhất về không gian, chỉ sử dụng một vài biến đơn giản để lưu trữ hai số Fibonacci trước đó và số hiện tại.

long long fibonacciOptimizedIterative(int k) {
    if (k <= 0) return 0;
    if (k == 1 || k == 2) return 1;

    long long prev_two = 1; // Đại diện cho F(i-2)
    long long prev_one = 1; // Đại diện cho F(i-1)
    long long current_fib = 1; // Đại diện cho F(i)

    for (int i = 3; i <= k; ++i) {
        current_fib = prev_one + prev_two;
        prev_two = prev_one;
        prev_one = current_fib;
    }
    return current_fib;
}

Độ phức tạp: Độ phức tạp thời gian là O(n) và độ phức tạp không gian là O(1). Đây là phương pháp được khuyến nghị cho hầu hết các trường hợp.

6. Dùng Công thức Binet

Dãy Fibonacci có thể được tính toán trực tiếp bằng công thức Binet, một công thức dạng đóng. Công thức này xuất phát từ việc giải phương trình đặc trưng của quan hệ truy hồi Fibonacci.

Công thức Binet là: $$ F_n = \frac{\phi^n - \psi^n}{\sqrt{5}} $$

Trong đó, $$ \phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887 \quad (\text{tỉ lệ vàng}) $$ và $$ \psi = \frac{1 - \sqrt{5}}{2} \approx -0.6180339887 $$

#include <cmath> // Cần thiết cho std::sqrt và std::pow

long long fibonacciBinetFormula(int k) {
    if (k <= 0) return 0;
    if (k == 1 || k == 2) return 1;

    const double SQRT5 = std::sqrt(5.0);
    const double PHI = (1.0 + SQRT5) / 2.0;
    const double PSI = (1.0 - SQRT5) / 2.0;
    
    // Sử dụng std::round để giảm thiểu lỗi làm tròn của số dấu phẩy động
    return static_cast<long long>(std::round((std::pow(PHI, k) - std::pow(PSI, k)) / SQRT5));
}

Độ phức tạp: Về mặt lý thuyết, độ phức tạp thời gian là O(log n) do hàm pow. Về mặt thực tế, đối với các kiểu dữ liệu dấu phẩy động độ chính xác cố định, nó thường được coi là O(1). Tuy nhiên, phương pháp này gặp vấn đề về độ chính xác của số dấu phẩy động (floating-point precision) đối với các số Fibonacci lớn, dẫn đến kết quả không chính xác.

7. Phương pháp Nâng lũy thừa ma trận (Matrix Exponentiation)

Phương pháp này sử dụng đại số tuyến tính để tính toán số Fibonacci thứ n trong thời gian logarit. Quan hệ truy hồi Fibonacci có thể được biểu diễn dưới dạng phép nhân ma trận:

$$ \begin{pmatrix} F_{k+1} \\ F_k \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_k \\ F_{k-1} \end{pmatrix} $$

Nếu áp dụng phép nhân ma trận này lặp đi lặp lại n-1 lần (với F₀=0, F₁=1), ta có:

$$ \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix} $$

Việc tính toán lũy thừa của ma trận A^(n-1) có thể được thực hiện hiệu quả bằng thuật toán lũy thừa nhị phân (binary exponentiation) trong thời gian O(log n).

struct Matrix {
    long long m00, m01, m10, m11; // Ma trận 2x2: |m00 m01|
                                 //             |m10 m11|

    Matrix(long long a = 0, long long b = 0, long long c = 0, long long d = 0)
        : m00(a), m01(b), m10(c), m11(d) {}
};

// Hàm nhân hai ma trận 2x2
Matrix multiplyMatrices(const Matrix& mat1, const Matrix& mat2) {
    return Matrix(
        mat1.m00 * mat2.m00 + mat1.m01 * mat2.m10,
        mat1.m00 * mat2.m01 + mat1.m01 * mat2.m11,
        mat1.m10 * mat2.m00 + mat1.m11 * mat2.m10,
        mat1.m10 * mat2.m01 + mat1.m11 * mat2.m11
    );
}

// Hàm tính lũy thừa ma trận M^exp bằng thuật toán lũy thừa nhị phân (O(log exp))
Matrix matrixPower(int exp) {
    Matrix result(1, 0, 0, 1); // Ma trận đơn vị (identity matrix)
    Matrix base(1, 1, 1, 0);   // Ma trận cơ sở cho Fibonacci

    while (exp > 0) {
        if (exp % 2 == 1) { // Nếu số mũ là lẻ
            result = multiplyMatrices(result, base);
        }
        base = multiplyMatrices(base, base); // Bình phương ma trận cơ sở
        exp /= 2;                            // Giảm một nửa số mũ
    }
    return result;
}

long long fibonacciMatrix(int k) {
    if (k <= 0) return 0;
    if (k == 1) return 1;

    // F_k là phần tử m00 của ma trận cơ sở lũy thừa (k-1)
    Matrix fib_matrix_pow = matrixPower(k - 1);
    return fib_matrix_pow.m00; // Trả về F_k
}

Độ phức tạp: Độ phức tạp thời gian là O(log n) và độ phức tạp không gian là O(1). Phương pháp này rất hiệu quả cho việc tính toán các số Fibonacci lớn.