获取以下递归实现的时间复杂度

/* Function to get diameter of a binary tree */ 
int diameter(struct node * tree) 
{ 
    /* base case where tree is empty */ 
    if (tree == 0) 
    return 0; 

    /* get the height of left and right sub-trees */ 
    int lheight = height(tree->left); 
    int rheight = height(tree->right); 

    /* get the diameter of left and right sub-trees */ 
    int ldiameter = diameter(tree->left); 
    int rdiameter = diameter(tree->right); 


    return max(lheight + rheight + 1, max(ldiameter, rdiameter)); 
} 


int height(struct node* node) 
{ 
    /* base case tree is empty */ 
    if(node == NULL) 
     return 0; 

    /* If tree is not empty then height = 1 + max of left 
     height and right heights */ 
    return 1 + max(height(node->left), height(node->right)); 
}

如何用此实现查找树的直径的时间复杂度是O（n^2），其中n是树中节点的数量？获取以下递归实现的时间复杂度

来源

2013-06-19 truly_geek

只是一个想法。我们不能记忆高度，我们是否应该每次计算？ – thefourtheye

我知道这个实施不是最佳的，我知道另一个O（n）的时间算法，但我需要了解这个实现的时间复杂度是如何为O（n^2）？ –

O（N）？那是什么？我知道一个算法是从根进行DFS并找到最远的节点（FN1）。然后做DFS从FN1中找出最远的节点，它会给出直径。 – thefourtheye

它是O（n^2），因为高度计算也是递归的。你可以写一个递归关系并解决它。

否则由Master's theorem

可以看到，F（n）是线性，因此C = 1 所以复杂性是登录a至b当a是4（递归使用4次）和b为2（在树的一半）

来源

2013-06-19 06:27:25

让D()表示diameter()和H()表示height()。为了方便，让我们假设二叉树是Complete Binary Tree，以便左子树和右子树具有相同数量的元素。让我们还假定二叉树中有N元素。现在直径函数的时间复杂度可以用下面的递推关系来表示。

D(N) = 2D(N/2) + 2H(N/2) + c1 ----- 1

因为在diameter()以下递归调用，

int lheight = height(tree->left); 
    int rheight = height(tree->right); 

    int ldiameter = diameter(tree->left); 
    int rdiameter = diameter(tree->right);

现在让我们来分析一下height()，

的递推关系表示的height()时间复杂度，

因为在height()以下递归调用，

return 1 + max(height(node->left), height(node->right));

现在H(N) = O(N logN)在1上2

替代应用主定理如此，我们得到，

D(N) = 2D(N/2) + c3 N logN + c1 ------ 3

使用解决大师定理，我们得到D(N) = O(N logN)。

所以递归函数diameter()的复杂性是O(N logN)

来源

2013-06-19 12:08:44 Deepu

获取以下递归实现的时间复杂度

回答

相关问题