Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
24 lines (18 sloc) 704 Bytes

2.71

                     {a b c d e} 31
                     /           \
                {a b c d} 15      e 16
                 /     \
           {a b c} 7    d 8
             /    \
        {a b} 3    c 4
         /   \
      a 1    b 2

上面是5个节点的情况,10个节点类似,每个非叶子节点有一个左子树与一个右子树,这是因为

1 + 2^2 + 2^3 + ... + 2^(n-2) = 2^(n-1)-1 < 2^(n-1)

2.72

最频繁的符号应该在树的最上面,只需要一次检查数的symbols即可,时间复杂度为O(n)

最不频繁的符号在树的最下面,需要检查n次树的symbols,时间复杂度为:

O(n) + O(n-1) + O(n-2) + ... + O(1) = O(n^2)