二叉树函数的最坏情况复杂度分析 "leaves"

Question

我想知道我的复杂性分析（n 的 T 最坏情况 elements/nodes）对于以下函数是否正确 Haskell（注意：wurzel = root；C = 常数因子）

--abstract data type for bin trees

data Bintree el = Empty
                  | Node {left :: Bintree el, root :: el, right :: Bintree el} 
                    deriving Show

--extract all leaves of a given Bintree (output: list)

leaves :: Bintree el -> [el]
leaves Empty = []
leaves (Node Empty root Empty) = [root]
leaves (Node left root right) = leaves left ++ leaves right

Answer 1

不是，错误很多。以下是一些比较明显的：

当你写T(n/2)+T(n/2)+T(n/4)+T(n/4)+...时，你似乎假设一半的节点在左分支，一半在右分支。这并不总是正确的——有些树是平衡的，但有些树肯定不是。
即使树是平衡的，也不只有2个大小为n/4的子树——有4个。同样有8个大小为n/8的子树，而不是2个。
描述 "dividing n by 2 i times" 的正确表达式是 n/(2^i)，而不是 n/(i^2)。此外，尽管有上述关于平衡的评论，您仍希望继续划分直到只到达一片叶子，因此省略号的正确基本情况是 T(n/n)，而不是 T(n/(2^n)) 或 [=17] =].
如果您重复除以二，然后将结果相加，如 n + n/2 + n/4 + n/8 + n/16 + ...，永远，您将得到 2*n，而不是 log_2(n)。
无论如何，这不适用，因为您没有添加 n 的倍数。 T(n) + T(n/2) + T(n/4) + T(n/8) + T(n/16) + ... 不一定与 T(2*n)（或 T(log_2(n))）有任何特殊关系。例如，假设 f(n) = 1。然后总和 f(1) + f(1/2) + f(1/4) + f(1/8) + f(1/16) + ... = 1 + 1 + 1 + 1 + 1 + ... 发散，即使 f(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...) = f(2) = 1.

二叉树函数的最坏情况复杂度分析 "leaves"

Worst case complexity analysis of a Binary Tree function "leaves"

binary-tree

haskell

time-complexity