Я немного смущен сравнением сложности между 2 двоичными деревьями, если они идентичны, ниже приведен код для того же

Question

Двоичное дерево, идентичное или нет другому коду двоичного дерева ниже, дает линейную сложность, т.е. большой O (n), где n - номер узла двоичного дерева с наименьшим количеством узлов.

 boolean identical(Node a, Node b)  
{ 
    if (a == null && b == null) 
        return true; 

    if (a != null && b != null)  
        return (a.data == b.data 
                && identical(a.left, b.left) 
                && identical(a.right, b.right)); 

    /* 3. one empty, one not -> false */
    return false; 
} 

(Фибоначчи серия с использованием рекурсии дает экспоненциальную сложность) Сложность приведенного ниже кода составляет 2 ^ n.

class Fibonacci  { 
    static int fib(int n) 
    { 
       if (n <= 1) 
         return n; 
       return fib(n-1) + fib(n-2); 
    } 
    public static void main (String args[]) 
    { 
       int n = 9; 
     }  
}

Мой вопрос: оба выглядят одинаково, но один имеет линейную сложность, а другой - экспоненциальную. Может ли кто-нибудь прояснить оба алгоритма.

Answer 1

Разница заключается в другом определении n . Хотя наивный рекурсивный алгоритм для чисел Фибоначчи также выполняет своего рода обход по графику, значение n определяется не количеством узлов в этом графе, а входным числом.

Однако при сравнении двоичного дерева n определяется как количество узлов.

Итак, n имеет совершенно другое значение в этих двух алгоритмах, и это объясняет, почему временная сложность в терминах n проявляется так по-разному.

Answer 2

Ряд Фибоначчи

Если вы построите дерево для рекурсивного кода для генерации ряда Фибоначчи, оно будет выглядеть так:

              fib(n)

      fib(n-1)      fib(n-2)

  fib(n-2) fib(n-3)   fib(n-3)  fib(n-4)

на каком уровне вы встретится с fib (1), чтобы дерево могло "остановиться"?

на ( n-1 ) уровне вы встретите fib(1), и на этом рекурсия остановится. Количество узлов будет порядка 2^n, потому что существует (n-1) уровней.

Сравнение двоичного дерева

Давайте рассмотрим ваше сравнение двоичного дерева.

Предположим, что оба являются полными двоичными деревьями. Согласно вашему алгоритму, он посетит все узлы один раз, и если «h» - это высота дерева, количество узлов будет порядка 2^h. Вы можете указать сложность в этом случае как O(2^h).

O(n) в этом случае эквивалентно O(2^h)