我有一个merge
函数,它花费O(log n)
的时间将两棵树合并成一棵树,还有一个listToTree
函数,它将初始元素列表转换为单例树,并重复对每个连续的树对调用merge
,直到只剩下一棵树。
相关函数签名和实现如下:
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
这是Chris Okasaki的《纯函数数据结构》中练习3.3的简化版。
根据练习,我现在要展示
listToTree
需要O(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))
的时间。我在进一步分析中遇到了麻烦。有人能给我一个正确的方向吗?