Big-O cho các triển khai Fibonacci khác nhau

Question

Tôi chỉ thử thực hiện mã (trong Java) cho các phương tiện khác nhau mà thuật ngữ thứ n của dãy Fibonacci có thể được tính toán và tôi hy vọng sẽ kiểm chứng những gì tôi đã học được.

Việc thực hiện lặp đi lặp lại như sau:

public int iterativeFibonacci(int n) 
{ 
    if (n == 1) return 0; 
    else if (n == 2) return 1; 
    int i = 0, j = 1, sum = 0; 
    for (; (n-2) != 0; --n) 
    { 
    sum = i + j; 
    i = j; 
    j = sum; 
    } 
    return sum; 
} 

Việc thực hiện đệ quy như sau: -

public int recursiveFibonacci(int n) 
    { 
    if (n == 1) return 0; 
    else if (n == 2) return 1; 
    return recursiveFibonacci(n-1) + recursiveFibonacci(n-2); 
    } 

Việc thực hiện memoized là như sau: -

public int memoizedFibonacci(int n) 
    { 
    if (n <= 0) return -1; 
    else if (n == 1) return 0; 
    else if (n == 2) return 1; 
    if (memory[n-1] == 0) 
     memory[n-1] = memoizedFibonacci(n-1); 
    if (memory[n-2] == 0) 
     memory[n-2] = memoizedFibonacci(n-2); 
    return memory[n-1]+memory[n-2]; 
    } 

tôi m có một chút nghi ngờ khi cố gắng tìm ra Big-O của những triển khai này. Tôi tin rằng triển khai lặp lại là O (n) khi vòng lặp qua N-2 lần.

Trong hàm đệ quy, có giá trị được tính toán lại, do đó, tôi nghĩ rằng đó là O (n^2).

Trong chức năng ghi nhớ, hơn một nửa giá trị được truy cập dựa trên ghi nhớ. Tôi đã đọc rằng một thuật toán là O (log N) nếu phải mất thời gian không đổi để giảm không gian vấn đề theo một phần và một thuật toán là O (N) nếu cần thời gian không đổi để giảm không gian vấn đề số tiền không đổi. Tôi có tin rằng việc triển khai được ghi nhớ là O (n) phức tạp không? Nếu vậy, sẽ không thực hiện lặp lại là tốt nhất trong số tất cả ba? (vì nó không sử dụng bộ nhớ bổ sung mà yêu cầu ghi nhớ).

Answer 1

Phiên bản đệ quy không phải là thời gian đa thức - số mũ là tightly bounded at φⁿ trong đó φ là tỷ lệ vàng (≈ 1.618034). Phiên bản đệ quy sẽ sử dụng bộ nhớ O (n) (mức sử dụng đến từ ngăn xếp).

Phiên bản ghi nhớ sẽ mất O (n) thời gian chạy đầu tiên, vì mỗi số chỉ được tính một lần. Tuy nhiên, để đổi lại, nó cũng mất O (n) bộ nhớ cho việc triển khai hiện tại của bạn (n xuất phát từ lưu trữ giá trị được tính và cũng cho ngăn xếp trong lần chạy đầu tiên). Nếu bạn chạy nó nhiều lần, mức độ phức tạp thời gian sẽ trở thành O (M + q), nơi M là tối đa của tất cả các đầu vào n và q là số truy vấn. Độ phức tạp của bộ nhớ sẽ trở thành O (M), xuất phát từ mảng chứa tất cả các giá trị được tính.

Việc thực hiện lặp đi lặp lại là tốt nhất nếu bạn xem xét một lần chạy thử, vì nó cũng chạy trong O (n), nhưng sử dụng lượng liên tục của bộ nhớ O (1) để tính toán. Đối với một số lượng lớn các lần chạy, nó sẽ tính toán lại mọi thứ, vì vậy hiệu suất của nó có thể không tốt bằng phiên bản ghi nhớ.

(Tuy nhiên, thực tế nói, lâu trước khi vấn đề hiệu suất và bộ nhớ, số có khả năng tràn cả số nguyên 64 bit, do đó, một phân tích chính xác phải tính đến thời gian cần thực hiện bổ sung nếu bạn đang tính toán số đầy đủ).

Như plesiv đề cập, số Fibonacci cũng có thể được tính toán trong O (log n) bằng cách nhân ma trận (bằng cách sử dụng thủ thuật tương tự lũy thừa càng nhanh bằng cách chia đôi số mũ ở mỗi bước).