列表到树函数的渐近运行时

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在Purely Functional Data Structures中的练习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 2 ^N = N我们有

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

(如果您想自己计算,请搜索"几何系列",或使用积分近似求和.)