Độ phức tạp của phương pháp #permutation và #repeated_permutation của Ruby là gì?

Question

Tôi đã tự hỏi về độ phức tạp của một số phương thức tích hợp sẵn của Ruby, hai phương pháp này nói riêng. Tôi nghĩ rằng tốt nhất tôi đã có thể đến với một phương pháp hoán vị của riêng tôi là Θ (n · n!), Ruby có tích hợp hoạt động tốt hơn không? Nếu có, hãy giúp tôi hiểu thuật toán của họ.

Answer 1

hoán vị

Array#permutation trả về một Enumerator với n! Mảng, vì vậy mức độ phức tạp thời gian sẽ có ít nhất O(n!).

tôi đã viết phương pháp này:

def slow_method(n) 
    (1..n).to_a.permutation.each do |p| 
    p 
    end 
end 

Nó không làm bất cứ điều gì với p, hy vọng buộc thế hệ của tất cả các hoán vị. Xây dựng một mảng của tất cả các hoán vị sẽ sử dụng quá nhiều bộ nhớ.

Phương pháp này được gọi là 10 lần đối với n từ 10 đến 13, và thời gian trung bình trong vài giây là:

t10 = 0.618895 
t11 = 6.7815425 
t12 = 82.896605 
t13 = 1073.015602 

O(n!) trông giống như một xấp xỉ hợp lý:

t13/fact(13)*fact(12)/t12 #=> 0.995694114280165 
t13/fact(13)*fact(11)/t11 #=> 1.0142685297667369 
t13/fact(13)*fact(10)/t10 #=> 1.0103498450722133 

O(n*n!) không :

t13/(fact(13)*13)*fact(12)*12/t12 #=> 0.9191022593355369 
t13/(fact(13)*13)*fact(11)*11/t11 #=> 0.8582272174949312 
t13/(fact(13)*13)*fact(10)*10/t10 #=> 0.777192188517087 

Thế hệ có vẻ là O(n!), nhưng làm bất cứ điều gì với các mảng tạo ra sẽ mang lại sự phức tạp tổng thể để O(n*n!).

Tại sao không phải là thế hệ O(n*n!)? Nó có thể đến từ thực tế là khi đệ quy tạo ra [1,2,3,4,5].permutation, các hoán vị còn lại là như nhau cho [1,2] và [2,1].

O(n!) đã quá chậm đến mức n sẽ không bao giờ lớn hơn 10, vì vậy, O(n*n!) không tệ hơn nhiều. Đối với n=20, n! là 2432902008176640000 và n*n! là 48658040163532800000.

Tiếp xúc nhiều lần hoán vị

[1,2,...n].repeated_permutation(k) tạo n**k Mảng của các yếu tố k.

Độ phức tạp phải là O(n**k) hoặc O(k*n**k).

Đối với k=n, nó sẽ trở thành O(n**n) hoặc O(n**(n+1)), thậm chí còn tệ hơn nhiều so với số permutation.

Answer 2

Có các thuật toán để tạo lặp lại tất cả các hoán vị của danh sách.

Làm cách nào? Thuật toán tạo tất cả các hoán vị của [1,2,3,4,...,n] theo thứ tự từ điển. Cho một hoán vị thuật toán tạo ra hoán vị từ vựng tiếp theo trong thời gian O(1).

Đây là những bước

• Tìm chỉ số lớn nhất k mà a[k] < a[k + 1], nếu không có chỉ số như vậy tồn tại các hoán vị là hoán vị cuối cùng
• Tìm chỉ số lớn nhất l lớn hơn k mà a[k] < a[l]
• Hoán đổi giá trị của a[k] với giá trị của a[l]
• Đảo ngược chuỗi từ a[k + 1] tối đa và bao gồm phần tử cuối cùng a[n]

Độ phức tạp là gì?

Mỗi bước là O(1) và có O(n!) hoán vị, vì vậy tổng độ phức tạp là O(n!).