रूबी की # जटिलता और #repeated_permutation विधियों में निर्मित समय की जटिलता क्या है?

Question

मैं रूबी के अंतर्निहित तरीकों में से कुछ की जटिलता के बारे में सोच रहा हूं, ये दोनों विशेष रूप से। मुझे लगता है कि मैं अपने आप पर एक क्रमपरिवर्तन विधि के लिए सबसे अच्छा आ गया हूं Θ (एन · एन!), रूबी का अंतर्निहित प्रदर्शन बेहतर करता है? यदि ऐसा है, तो कृपया मुझे उनके एल्गोरिदम को समझने में मदद करें।

Answer 1

क्रमपरिवर्तन

Array#permutationn! सरणी के साथ एक गणनाकार देता है, इसलिए समय जटिलता कम से कम O(n!) हो जाएगा।

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

यह p साथ कुछ भी नहीं है, सभी क्रमपरिवर्तन की पीढ़ी के लिए मजबूर उम्मीद:

मैं इस विधि लिखा था। सभी क्रमिकरणों के एक ऐरे का निर्माण बहुत अधिक स्मृति का उपयोग करेगा।

इस विधि सेकंड में 10 और 13, और औसत बार के बीच n के लिए 10 बार बुलाया गया था थे:

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!) नहीं करता है:

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

O(n!) एक उचित सन्निकटन की तरह दिखता है :

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 

पीढ़ी प्रतीत होता है O(n!), लेकिन जेनरेट किए गए Arrays के साथ कुछ भी करने से समग्र जटिलता O(n*n!) पर आ जाएगी।

पीढ़ी O(n*n!) क्यों नहीं है? यह इस तथ्य से आ सकता है कि जब [1,2,3,4,5].permutation को पुन: उत्पन्न करते हैं, तो शेष क्रमपरिवर्तन [1,2] और [2,1] के लिए समान होते हैं।

O(n!) पहले से ही धीमा है कि n 10 से अधिक बड़ा नहीं होगा, इसलिए O(n*n!) अधिक खराब नहीं है। n=20 के लिए, n!2432902008176640000 और n*n!48658040163532800000 है।

दोहराया क्रमपरिवर्तन

[1,2,...n].repeated_permutation(k) कश्मीर तत्वों की n**k सरणी उत्पन्न करता है।

जटिलता या तो O(n**k) या O(k*n**k) होना चाहिए।

k=n के लिए, यह O(n**n) या O(n**(n+1)) बन जाता है, जो permutation के मुकाबले भी (अधिक) खराब है।

Answer 2

एक सूची के सभी क्रमपरिवर्तन उत्पन्न करने के लिए एल्गोरिदम हैं।

कैसे? एल्गोरिदम लेक्सिकोग्राफिक ऑर्डर में [1,2,3,4,...,n] के सभी क्रमपरिवर्तन उत्पन्न करता है। एक क्रमपरिवर्तन को देखते हुए एल्गोरिदम O(1) समय में अगली शब्दावली क्रमपरिवर्तन उत्पन्न करता है।

ये कदम हैं ऐसी कोई सूचकांक मौजूद क्रमचय पिछले क्रमचय

है सबसे बड़ा सूचकांक खोजें

• , सबसे बड़ी सूची k ऐसी है कि a[k] < a[k + 1] खोजें a[k] < a[l]
l से अधिक k ऐसा है कि
• के मान को a[l]
• से अनुक्रम को उलट देंतक अंतिम तत्व a[n]

जटिलता क्या है?

प्रत्येक चरण O(1) है और O(n!) क्रमपरिवर्तन हैं, इसलिए कुल जटिलता O(n!) है।