6
我有一個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
這是純功能性數據結構由克里斯·奧卡薩基鍛鍊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))
我無法德任何進一步的分析。任何人都可以給我一個正確的方向提示嗎？