Phiên bản lặp lại và đệ quy có cùng độ phức tạp?

Question

Liệu các phiên bản lặp lại và đệ quy của hai thuật toán có cùng độ phức tạp không? Nói ví dụ các phiên bản lặp lại và đệ quy của dãy Fibonacci.

Answer 1

Câu trả lời phụ thuộc rất nhiều vào việc triển khai của bạn. Đối với ví dụ bạn đưa ra có một số giải pháp có thể và tôi sẽ nói rằng cách ngây thơ để thực hiện một giải pháp có độ phức tạp tốt hơn khi được thực hiện lặp lại. Dưới đây là hai ngôn ngữ này:

int iterative_fib(int n) { 
    if (n <= 2) { 
    return 1; 
    } 
    int a = 1, b = 1, c; 
    for (int i = 0; i < n - 2; ++i) { 
    c = a + b; 
    b = a; 
    a = c; 
    } 
    return a; 
} 
int recursive_fib(int n) { 
    if (n <= 2) { 
    return 1; 
    } 
    return recursive_fib(n - 1) + recursive_fib(n-2); 
} 

Trong cả hai hiện thực tôi cho rằng một ví dụ đầu vào đúng n> = 1. Các mã đầu tiên là lâu hơn nữa nhưng phức tạp của nó là O (n) tức là tuyến tính, trong khi thực hiện thứ hai là ngắn hơn nhưng có độ phức tạp theo hàm mũ O (fib (n)) = O (φ^n) (φ = (1+√5)/2) và do đó chậm hơn nhiều. Người ta có thể cải thiện phiên bản đệ quy bằng cách giới thiệu ghi nhớ (nghĩa là nhớ giá trị trả lại của hàm bạn đã tính toán). Điều này thường được thực hiện bằng cách giới thiệu một mảng nơi bạn lưu trữ các giá trị. Dưới đây là ví dụ:

int mem[1000]; // initialize this array with some invalid value. Usually 0 or -1 
       // as memset can be used for that: memset(mem, -1, sizeof(mem)); 
int mem_fib(int n) { 
    if (n <= 2) { 
    return mem[n] = 1; 
    } 
    if (mem[n-1] == -1) { 
    solve(n-1); 
    } 
    if (mem[n-2] == -1) { 
    solve(n-2); 
    } 
    return mem[n] = mem[n-1] + mem[n-2]; 
} 

Đây là độ phức tạp của thuật toán đệ quy tuyến tính giống như giải pháp lặp. Giải pháp tôi đã giới thiệu ở trên là cách tiếp cận từ trên xuống cho giải pháp lập trình động của vấn đề của bạn. Cách tiếp cận từ dưới lên sẽ dẫn đến một cái gì đó rất giống với giải pháp tôi đã giới thiệu như là lặp đi lặp lại. Có rất nhiều bài viết về lập trình động bao gồm trong wikipedia

Tùy thuộc vào các vấn đề tôi gặp trong trải nghiệm của mình một số cách khó giải quyết hơn với cách tiếp cận từ dưới lên (nghĩa là giải pháp lặp). với cách tiếp cận từ trên xuống. Tuy nhiên, lý thuyết nói rằng mỗi vấn đề mà có một giải pháp lặp lại có đệ quy với độ phức tạp tính toán tương tự (và ngược lại).

Hy vọng câu trả lời này sẽ hữu ích.

Answer 2

Có, nếu bạn sử dụng chính xác cùng một ý tưởng nằm trong thuật toán, điều đó không quan trọng. Tuy nhiên, đệ quy thường dễ sử dụng liên quan đến lặp lại. Ví dụ, viết một phiên bản đệ quy của các tòa tháp của Hà Nội là khá dễ dàng. Việc chuyển đổi phiên bản đệ quy thành một phiên bản lặp tương ứng là khó khăn và dễ bị lỗi mặc dù nó có thể được thực hiện. Trên thực tế, có một định lý cho biết rằng mọi thuật toán đệ quy có thể được chuyển thành một phép lặp tương đương (làm điều này yêu cầu bắt chước đệ quy lặp lại bằng cách sử dụng một hoặc nhiều cấu trúc dữ liệu ngăn xếp để giữ các tham số được chuyển tới các lời gọi đệ quy).

Answer 3

Nếu bạn thực hiện một số thuật toán đệ quy, bạn có thể chuyển đổi nó thành lặp lại bằng cách lưu trữ tất cả các biến cục bộ chức năng trong một mảng, mô phỏng hiệu quả ngăn xếp trên heap. Nếu thực hiện như thế này không có sự khác biệt giữa lặp đi lặp lại và đệ quy.

Lưu ý rằng có ít nhất hai thuật toán Fibonacci đệ quy, do đó, ví dụ chính xác, bạn cần phải xác định thuật toán đệ quy mà bạn đang nói đến.

Answer 4

Có, mọi thuật toán lặp lại có thể được chuyển thành phiên bản đệ quy và ngược lại. Một cách bằng cách chuyển tiếp các bước tiếp theo và cách khác bằng cách thực hiện cấu trúc ngăn xếp. Điều này được thực hiện mà không tăng độ phức tạp về thời gian.

Nếu bạn có thể tối ưu hóa đệ quy đuôi thì mọi thuật toán lặp lại có thể được chuyển thành đệ quy mà không làm tăng độ phức tạp của bộ nhớ tiệm cận.

Answer 5

Thuật toán đệ quy cụ thể cho chuỗi fibanocci tính toán kém hiệu quả hơn. Hãy xem xét các tình huống sau đây của việc tìm kiếm fib (4) thông qua các thuật toán đệ quy

   int fib(n) : 
         if(n==0 || n==1) 
          return n; 
         else 
          return fib(n-1) + fib(n-2) 

Bây giờ khi các thuật toán trên thực hiện đối với n = 4

      fib(4) 

        fib(3)    fib(2) 

       fib(2) fib(1)  fib(1) fib(0) 

      fib(1) fib(0) 

Đó là một cái cây. Nó nói rằng để tính toán fib (4) bạn cần phải tính toán fib (3) và fib (2) và vân vân.

Lưu ý rằng ngay cả đối với một giá trị nhỏ 4, fib (2) được tính hai lần và fib (1) được tính ba lần. Số lượng bổ sung này tăng lên với số lượng lớn.

Có một giả thuyết rằng số lượng bổ sung cần thiết cho việc tính toán fib (n) là

     fib(n+1) -1 

Vì vậy, sự trùng lặp này là một trong đó là nguyên nhân của giảm hiệu suất trong thuật toán đặc biệt này.

Thuật toán lặp lại cho chuỗi mã hóa nhanh hơn đáng kể vì nó không liên quan đến tính toán những thứ thừa.

Mặc dù vậy, tất cả các thuật toán có thể không giống nhau.