Độ phức tạp trong thuật toán đệ quy

Question

Tôi hiện đang nghiên cứu cấu trúc dữ liệu tại trường đại học và tình cờ gặp một câu hỏi về sự phức tạp trong đệ quy.

Với mã này:

Unsigned func (unsigned n) 
{ 
if (n ==0) return 1; 
if(n==1) return 2; 

\\do somthing(in O(1)) 

return func(n-1) + func(n-1); 
} 

Tôi biết những gì mã lệnh thực hiện. Tôi biết rằng trong hình thức bây giờ, độ phức tạp thời gian là O (2^n).

Tuy nhiên, câu hỏi của tôi là: độ phức tạp của thời gian sẽ thay đổi nếu thay vì lệnh gọi lại cuối cùng của mã tôi sẽ viết: return 2*func(n-1)?

Tôi biết rằng về độ phức tạp của bộ nhớ, chúng ta đang nói về sự giảm đáng kể không gian được thực hiện bởi đệ quy, nhưng theo thời gian phức tạp, sẽ có thay đổi gì không?

Tôi đã làm toán bằng cách sử dụng hàm đệ quy và hiểu rằng sẽ không có sự thay đổi về độ phức tạp của thời gian, tôi có đúng không?

Answer 1

Phương pháp này được chỉ có O(n), bởi vì nếu bạn chạy nó với 5, nó đi đến đệ quy với 4, sau đó với 3, vv

Unsigned func (unsigned n) 
{ 
if (n ==0) return 1; 
if(n==1) return 2; 

\\do somthing(in O(1)) 

return 2*func(n-1); 
} 

Tuy nhiên những gì về vấn đề này:

Unsigned func (unsigned n) 
{ 
if (n ==0) return 1; 
if(n==1) return 2; 

\\do somthing(in O(1)) 

return func(n-1) + func(n-1); 
} 

Ví dụ func (5) nó sẽ thực hiện trước tiên như sau

5 -> 4 -> 3 -> 2 -> 1 

Sau đó, nó trở về 2, nhưng có nó sẽ thực hiện phần "thứ hai", vì vậy toàn bộ quá trình trông giống như

5 -> 4 -> 3 -> 2-> 1; 2-> 1; 3->2->1; etc. 

Do đó KHÔNG thay đổi phức tạp đáng kể từ O(n) để O(2^n)

---

Hãy thử ví dụ thực tế mã này:

public class Complexity { 
    private static int counter; 
    public static void main(String[] args) { 
     for (int i = 0; i < 20; i++) { 
      counter = 0; 
      func(i); 
      System.out.println("For n="+i+" of 2*func the number of cycles is " + counter); 
      counter = 0; 
      func2(i); 
      System.out.println("For n="+i+" of func + func the number of cycles is " + counter); 
     } 
    } 

    public static int func(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     } 
     return 2 * func(n - 1); 
    } 

    public static int func2(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     } 
     return func2(n - 1) + func2(n - 1); 
    }  
} 

Có đầu ra này:

For n=0 of 2*func the number of cycles is 1 
For n=0 of func + func the number of cycles is 1 
For n=1 of 2*func the number of cycles is 1 
For n=1 of func + func the number of cycles is 1 
For n=2 of 2*func the number of cycles is 2 
For n=2 of func + func the number of cycles is 3 
For n=3 of 2*func the number of cycles is 3 
For n=3 of func + func the number of cycles is 7 
For n=4 of 2*func the number of cycles is 4 
For n=4 of func + func the number of cycles is 15 
For n=5 of 2*func the number of cycles is 5 
For n=5 of func + func the number of cycles is 31 
For n=6 of 2*func the number of cycles is 6 
For n=6 of func + func the number of cycles is 63 
For n=7 of 2*func the number of cycles is 7 
For n=7 of func + func the number of cycles is 127 
For n=8 of 2*func the number of cycles is 8 
For n=8 of func + func the number of cycles is 255 
For n=9 of 2*func the number of cycles is 9 
For n=9 of func + func the number of cycles is 511 
For n=10 of 2*func the number of cycles is 10 
For n=10 of func + func the number of cycles is 1023 
For n=11 of 2*func the number of cycles is 11 
For n=11 of func + func the number of cycles is 2047 
For n=12 of 2*func the number of cycles is 12 
For n=12 of func + func the number of cycles is 4095 
For n=13 of 2*func the number of cycles is 13 
For n=13 of func + func the number of cycles is 8191 
For n=14 of 2*func the number of cycles is 14 
For n=14 of func + func the number of cycles is 16383 
For n=15 of 2*func the number of cycles is 15 
For n=15 of func + func the number of cycles is 32767 
For n=16 of 2*func the number of cycles is 16 
For n=16 of func + func the number of cycles is 65535 
For n=17 of 2*func the number of cycles is 17 
For n=17 of func + func the number of cycles is 131071 
For n=18 of 2*func the number of cycles is 18 
For n=18 of func + func the number of cycles is 262143 
For n=19 of 2*func the number of cycles is 19 
For n=19 of func + func the number of cycles is 524287 

---

Nhưng nếu bạn nhớ kết quả đã tính toán, mức độ phức tạp vẫn là O(n) thậm chí với cách tiếp cận thứ hai:

public class Complexity { 
    private static int counter; 
    private static int[] results; 

    public static void main(String[] args) { 
     for (int i = 0; i < 20; i++) { 
      counter = 0; 
      func(i); 
      System.out.println("For n="+i+" of 2*func the number of cycles is " + counter); 
      counter = 0; 
      func2(i); 
      System.out.println("For n="+i+" of func + func the number of cycles is " + counter); 
      counter = 0; 
      results = new int[i+1]; 
      func3(i); 
      System.out.println("For n="+i+" of func + func with remembering the number of cycles is " + counter); 
     } 
    } 

    public static int func(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     } 
     return 2 * func(n - 1); 
    } 

    public static int func2(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     }   
     return func2(n - 1) + func2(n - 1); 
    } 

    public static int func3(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     } 

     if (results[n] == 0){ 
      results[n] = func3(n - 1) + func3(n - 1); 
     } 

     return results[n]; 
    }   
} 

Có kết quả này:

For n=0 of 2*func the number of cycles is 1 
For n=0 of func + func the number of cycles is 1 
For n=0 of func + func with remembering the number of cycles is 1 
For n=1 of 2*func the number of cycles is 1 
For n=1 of func + func the number of cycles is 1 
For n=1 of func + func with remembering the number of cycles is 1 
For n=2 of 2*func the number of cycles is 2 
For n=2 of func + func the number of cycles is 3 
For n=2 of func + func with remembering the number of cycles is 3 
For n=3 of 2*func the number of cycles is 3 
For n=3 of func + func the number of cycles is 7 
For n=3 of func + func with remembering the number of cycles is 5 
For n=4 of 2*func the number of cycles is 4 
For n=4 of func + func the number of cycles is 15 
For n=4 of func + func with remembering the number of cycles is 7 
For n=5 of 2*func the number of cycles is 5 
For n=5 of func + func the number of cycles is 31 
For n=5 of func + func with remembering the number of cycles is 9 
For n=6 of 2*func the number of cycles is 6 
For n=6 of func + func the number of cycles is 63 
For n=6 of func + func with remembering the number of cycles is 11 
For n=7 of 2*func the number of cycles is 7 
For n=7 of func + func the number of cycles is 127 
For n=7 of func + func with remembering the number of cycles is 13 
For n=8 of 2*func the number of cycles is 8 
For n=8 of func + func the number of cycles is 255 
For n=8 of func + func with remembering the number of cycles is 15 
For n=9 of 2*func the number of cycles is 9 
For n=9 of func + func the number of cycles is 511 
For n=9 of func + func with remembering the number of cycles is 17 
For n=10 of 2*func the number of cycles is 10 
For n=10 of func + func the number of cycles is 1023 
For n=10 of func + func with remembering the number of cycles is 19 
For n=11 of 2*func the number of cycles is 11 
For n=11 of func + func the number of cycles is 2047 
For n=11 of func + func with remembering the number of cycles is 21 
For n=12 of 2*func the number of cycles is 12 
For n=12 of func + func the number of cycles is 4095 
For n=12 of func + func with remembering the number of cycles is 23 
For n=13 of 2*func the number of cycles is 13 
For n=13 of func + func the number of cycles is 8191 
For n=13 of func + func with remembering the number of cycles is 25 
For n=14 of 2*func the number of cycles is 14 
For n=14 of func + func the number of cycles is 16383 
For n=14 of func + func with remembering the number of cycles is 27 
For n=15 of 2*func the number of cycles is 15 
For n=15 of func + func the number of cycles is 32767 
For n=15 of func + func with remembering the number of cycles is 29 
For n=16 of 2*func the number of cycles is 16 
For n=16 of func + func the number of cycles is 65535 
For n=16 of func + func with remembering the number of cycles is 31 
For n=17 of 2*func the number of cycles is 17 
For n=17 of func + func the number of cycles is 131071 
For n=17 of func + func with remembering the number of cycles is 33 
For n=18 of 2*func the number of cycles is 18 
For n=18 of func + func the number of cycles is 262143 
For n=18 of func + func with remembering the number of cycles is 35 
For n=19 of 2*func the number of cycles is 19 
For n=19 of func + func the number of cycles is 524287 
For n=19 of func + func with remembering the number of cycles is 37 

Answer 2

Nó phụ thuộc vào ngữ nghĩa của ngôn ngữ lập trình/thuật toán của bạn.

Nếu theo số f(n), bạn có nghĩa là "gọi hàm bất kể nó được gọi với cùng một đối số trước" (vì đó là trường hợp với hầu hết các ngôn ngữ lập trình), thì thay đổi của bạn sẽ giảm độ phức tạp xuống O (n) . Bạn có một cuộc gọi hàm O (1) cho mỗi lần giảm đối số.

Nếu không (nếu bạn đang nói về các hàm thuần túy và ghi nhớ các kết quả đã biết), cả hai thuật toán đều có độ phức tạp O (n).