2017-01-13 36 views
9

Cho một tập hợp các số riêng biệt, trả về tất cả các hoán vị có thể.Độ phức tạp theo thời gian của hàm hoán vị

Ví dụ, [1,2,3] có hoán vị sau:
[[1,2,3], [1,3,2], [2,1,3], [2 , 3,1], [3,1,2], [3,2,1]]

giải pháp lặp của tôi là:

public List<List<Integer>> permute(int[] nums) { 
     List<List<Integer>> result = new ArrayList<>(); 
     result.add(new ArrayList<>()); 
     for(int i=0;i<nums.length;i++) 
     { 
      List<List<Integer>> temp = new ArrayList<>(); 
      for(List<Integer> a: result) 
      { 
       for(int j=0; j<=a.size();j++) 
       { 
        a.add(j,nums[i]); 
        List<Integer> current = new ArrayList<>(a); 
        temp.add(current); 
        a.remove(j); 
       } 
      } 
      result = new ArrayList<>(temp); 
     } 
     return result; 
    } 

giải pháp đệ quy của tôi là:

public List<List<Integer>> permuteRec(int[] nums) { 
     List<List<Integer>> result = new ArrayList<List<Integer>>(); 
     if (nums == null || nums.length == 0) { 
      return result; 
     } 
     makePermutations(nums, result, 0); 
     return result; 
    } 


void makePermutations(int[] nums, List<List<Integer>> result, int start) { 
    if (start >= nums.length) { 
     List<Integer> temp = convertArrayToList(nums); 
     result.add(temp); 
    } 
    for (int i = start; i < nums.length; i++) { 
     swap(nums, start, i); 
     makePermutations(nums, result, start + 1); 
     swap(nums, start, i); 
    } 
} 

private ArrayList<Integer> convertArrayToList(int[] num) { 
     ArrayList<Integer> item = new ArrayList<Integer>(); 
     for (int h = 0; h < num.length; h++) { 
      item.add(num[h]); 
     } 
     return item; 
    } 

Theo tôi độ phức tạp thời gian (lớn-Oh) của giải pháp lặp của tôi là: n * n (n + 1)/2 ~ O (n^3)
Tôi không thể tìm ra độ phức tạp của đệ quy dung dịch.
Bất cứ ai có thể giải thích sự phức tạp của cả hai?

+3

Số hoán vị cho các phần tử n là n !, do đó, một thuật toán để tạo tất cả n! hoán vị sẽ có độ phức tạp thời gian O (n!). – rcgldr

+0

cho cả đệ quy và lặp lại? – ojas

+1

@OJASJUNEJA có. Đây là thời gian chạy tốt nhất có thể hình dung được cho vấn đề này. Hãy tưởng tượng nếu bạn có một máy phát điện ma thuật mà chỉ phun ra một hoán vị mỗi 1 giây. Bạn vẫn cần phải đợi 'n!' Giây để máy phát điện này kết thúc vì có hoán vị 'n!'. – nem035

Trả lời

1

Giải pháp đệ quy có độ phức tạp là O(n!) vì nó được điều chỉnh theo phương trình: T(n) = n * T(n-1) + O(1).

Giải pháp lặp lại có ba vòng lồng nhau và do đó có độ phức tạp là O(n^3).

Tuy nhiên, giải pháp lặp lại sẽ không tạo ra hoán vị chính xác cho bất kỳ số nào ngoài số 3.

Đối với n = 3, bạn có thể thấy rằng n * (n - 1) * (n-2) = n!. LHS là O(n^3) (hoặc thay vì O(n^n) kể từ n=3 tại đây) và RHS là O(n!).

Để có giá trị lớn hơn về kích thước của danh sách, hãy nói n, bạn có thể có n vòng lồng nhau và sẽ cung cấp hoán vị hợp lệ. Sự phức tạp trong trường hợp đó sẽ là O(n^n) và lớn hơn nhiều so với O(n!), hoặc đúng hơn là n! < n^n. Có một mối quan hệ khá tốt đẹp được gọi là Stirling's approximation giải thích mối quan hệ này.

3

Đó là đầu ra (đó là rất lớn) các vấn đề trong vấn đề này, không phải là thực hiện thường xuyên. Đối với n các mục riêng biệt, có n! hoán vị được trả về làm câu trả lời và do đó chúng tôi có ít nhất O(n!) độ phức tạp.

Với sự giúp đỡ của Stirling's approximation

O(n!) = O(n^(1/2+n)/exp(n)) = O(sqrt(n) * (n/e)^n) 

chúng ta có thể dễ dàng nhận thấy, rằng O(n!) > O(n^c) cho bất kỳ liên tục c, đó là lý do tại sao nó không quan trọng nếu việc thực hiện bản thân thêm một O(n^3) từ

O(n!) + O(n^3) = O(n!) 
Các vấn đề liên quan