大门|大门-CS-2004 |问题85

一个程序以一个具有n个叶节点的平衡二叉搜索树作为输入，计算每个节点x的函数g（x）的值。如果计算g（x）的代价是x的左子树中的叶节点数最小，x的右子树中的叶节点数最小，则程序的最坏情况时间复杂度为 （A） Θ（n） （B） Θ（nLogn） （C） Θ（n） ^2. ) （D） Θ（n） ^2. 日志（n） 答复: （B） 说明：

The recurrence relation for the recursive function is
T(N) = 2 * T(N/2) + n/2
Where N is the total no. of nodes in the tree.
T(N) = 2 * (2*T(N/2) + n/2) + n/2
     = 4 * T(N/2) + 3(n/2)
Solve this till T(1) i.e. till we reach the root.
T(N) = c * T(N / 2^i) + (2*i - 1) * (n/2)
Where i = lg(N)
= lg((2n - 1) / 2)
O(c * T(N / 2^i) + (2*i - 1) * (n/2)) reduces to
O((2*i - 1) * (n/2))
O((2*( lg((2n - 1) / 2)) - 1) * (n/2)) ...sub the value of i.
O(n * ln(n)) 

资料来源： http://www.nid.iitkgp.ernet.in/DSamanta/courses/IT60101_2/Archives/Assignment-%20IC%20Binary%20Trees%20Solutions.pdf 这个问题的小测验