Почему сложность во времени этой функции проверяет баланс двоичного дерева O (n log n)?

Question

Запрос от взлома кодирования Интервью с Гейл Лакманн Макдауэлл:

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

(Пример реализации ниже.)

Вопрос: Можете ли вы помочь мне понять, почему автор утверждает, что isBalanced имеет временную сложность O(n log n)?Я получаю это в некоторой степени и могу запомнить это очень хорошо, но я не могу понять, почему это так, как я могу для других временных сложностей, таких как O(n^2).

int getHeight(TreeNode root) {
  if (root == null) { return -1; }
  return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

boolean isBalanced(TreeNode root) {
  if (root == null) { return true; }

  int heightDiff = getHeight(root.left) - getHeight(root.right);
  if (Maths.abs(heightDiff) > 1) {
    return false;
  } else {
    return isBalanced(root.left) && isBalanced(root.right);
  }
}

// isBalanced([some node]) --> true/false

Как я могу визуализировать почемуisBalanced считается O(n log n)?

Answer 1

Допустим, у вас есть BST

      4        // No of nodes 1
    /    \
   2      6    // No of nodes 2
 /  \    /  \
1    3  5    7 // No of nodes 4

Ваша функция isBalanced проходит через все узлы, включая те, у которых нет дочерних элементов, и вызывает getHeight, чтобы вычислить высоту левого и правого дочерних элементов.

Рекурсивное отношение функции будет

, которое получено из основной теоремы

a = количество подзадач в рекурсии

n/b = размер каждой подзадачи

f(n) = стоимостьработы, которая должна быть выполнена вне рекурсивных вызовов

a - это 2, потому что мы должны посетить оба дочерних узла каждого родителя

b - это 2, потому что есливы замечаете, что число узлов уменьшается вдвое каждый раз, когда вы переходите на уровень выше (снизу).

f(n) равно n, потому что нам нужно вызвать getHeight() на каждом узле

Что удовлетворяет второму случаю основной теоремы:

Установка значений для доказательства f(n) = O(n^logb(a))

Таким образом, мы получаем сложность времени O(n log n)