獲取以下遞歸實現的時間複雜度

/* 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

獲取以下遞歸實現的時間複雜度

回答

相關問題