列表转树函数的渐近运行时间

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)的时间。但是我做不到。:-( 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))的时间。

我在进一步分析中遇到了麻烦。有人能给我一个正确的方向吗？

- Deestan

Answer 1

就快完成了。你已经知道表达式是

所以唯一的问题是求这个和。使用log(AB) = log A + log B 和 log 2^N = N，我们得到

借助计算器的帮助，我们可以发现X = O(2^m) = O(n)，这是预期的。

（如果你想自己计算，请搜索“等比数列”，或者使用积分近似求和。）

- kennytm