Блог

Я пытался понять и реализовать основную теорему для нахождения временной сложности рекуррентных отношений.

Но я не могу понять, как мы можем вычислить временную сложность алгоритма, используя его.

Рассмотрим этот алгоритм для нахождения диаметра двоичного дерева

 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) (первый случай основной теоремы).