मैं एक merge समारोह जो एक में दो पेड़ों गठबंधन करने के लिए समय O(log n) लेता है, और एक listToTree समारोह जो सिंगलटन पेड़ों के लिए तत्वों का एक प्रारंभिक सूची में कनवर्ट करता है और बार बार प्रत्येक अगली जोड़ी पर merge कॉल पेड़ के पेड़ तक केवल एक पेड़ बना रहता है।सूची करने के लिए पेड़ समारोह के लिए Asymptotic क्रम
समारोह हस्ताक्षर और प्रासंगिक कार्यान्वयन इस प्रकार हैं:
merge :: Tree a -> Tree a -> Tree a --// O(log n) where n is size of input trees
singleton :: a -> Tree a --// O(1)
empty :: Tree a --// O(1)
listToTree :: [a] -> Tree a --// Supposedly O(n)
listToTree = listToTreeR . (map singleton)
listToTreeR :: [Tree a] -> Tree a
listToTreeR [] = empty
listToTreeR (x:[]) = x
listToTreeR xs = listToTreeR (mergePairs xs)
mergePairs :: [Tree a] -> [Tree a]
mergePairs [] = []
mergePairs (x:[]) = [x]
mergePairs (x:y:xs) = merge x y : mergePairs xs
यह एक थोड़ा सरलीकृत क्रिस ओकासाकी द्वारा पूरी तरह कार्यात्मक डेटा स्ट्रक्चर में व्यायाम 3.3 का संस्करण है।
अभ्यास के अनुसार, अब मैं दिखाऊंगा कि listToTreeO(n) समय लेता है। जो मैं नहीं कर सकता :-(
वहाँ तुच्छता listToTreeR करने के लिए ceil(log n) पुनरावर्ती कॉल, mergePairs करने के लिए ceil(log n) कॉल अर्थ हैं।
mergePairs का चलने का समय सूची की लंबाई, और पेड़ों की आकार। की लंबाई पर निर्भर है सूची 2^h-1 है, और पेड़ों की आकार log(n/(2^h)), जहां h=log n पहले पुनरावर्ती कदम है कर रहे हैं, और h=1 पिछले पुनरावर्ती कदम है। mergePairs को प्रत्येक कॉल इस प्रकार समय लगता है (2^h-1) * log(n/(2^h))
मैं मुसीबत तक आ रही है इस विश्लेषण को आगे बढ़ाएं। क्या कोई मुझे सही दिशा में संकेत दे सकता है?