我试图理解并实现主定理来找出递归关系的时间复杂度。
但是，我无法理解我们如何计算使用它的算法的时间复杂度。
考虑这个算法来查找二叉树的直径
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
/* Class to print the Diameter */
class BinaryTree
{
Node root;
/* Method to calculate the diameter and return it to main */
int diameter(Node root)
{
/* base case if tree is empty */
if (root == null)
return 0;
/* get the height of left and right sub trees */
int lheight = height(root.left);
int rheight = height(root.right);
/* get the diameter of left and right subtrees */
int ldiameter = diameter(root.left);
int rdiameter = diameter(root.right);
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return Math.max(lheight + rheight + 1,
Math.max(ldiameter, rdiameter));
}
/* A wrapper over diameter(Node root) */
int diameter()
{
return diameter(root);
}
/*The function Compute the "height" of a tree. Height is the
number f nodes along the longest path from the root node
down to the farthest leaf node.*/
static int height(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 + Math.max(height(node.left), height(node.right)));
}
public static void main(String args[])
{
/* creating a binary tree and entering the nodes */
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("The diameter of the given binary tree is: "
+ tree.diameter());
}
}
我知道上述算法的时间复杂度是O(n^2) 只要看着它。由于单个递归调用每个节点的时间很多。
如何使用主方法找到该算法的时间复杂度？
我在计算递归函数的时间复杂度方面完全是新手。 我认为主定理是一种计算递归函数时间复杂度的方法。
如何使用主方法或任何其他方法找到递归算法的时间复杂度？
如果有人能教我如何求递归函数的时间复杂度，那将是一个很大的帮助。
谢谢!
最佳答案
如果我们假设二叉树是平衡的，则总时间复杂度为T(n)，并且T(n) = 2T(n/2) + 2T(n/2 ) + 1。第一个 2T(n/2) 表示直径(左和右)，第二个 2T(n/2) 表示高度(左和右高度)。因此 T(n) = 4T(n/2) + 1 = O(n^2) ( master theorem 的第一种情况)。
关于algorithm - 求递归关系时间复杂度的主定理，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55025056/