haskell - list-to-tree 函数的渐近运行时

Question

我有一个 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)时间。我不能。 :-(

有琐碎的ceil(log n)递归调用 listToTreeR , 意思是 ceil(log n)调用mergePairs .
mergePairs的运行时间|取决于列表的长度和树的大小。列表长度为2^h-1 ，树的大小为 log(n/(2^h)) , 其中 h=log n是第一个递归步骤，h=1是最后一个递归步骤。每次调用mergePairs因此需要时间(2^h-1) * log(n/(2^h))
我无法进一步进行此分析。谁能给我一个正确方向的提示？

Answer 1

快到了。你已经知道表达式是

所以唯一的问题是评估这个总和。使用 log(AB) = log A + log B 和 log 2N = N 我们有

With help of calculators ，我们可以发现 X = O(2m) = O(n)，这是预期的。

(如果您想自己计算，请搜索“几何级数”，或使用积分近似总和。)