Объясните, почему этот алгоритм обхода бинарного дерева имеет O (NlogN) сложность по времени?

Question

Я сейчас изучаю книгу «Взломать кодирование» и выполняю упражнение по бинарному дереву.Существует фрагмент кода, который соответствует книге O(NlogN), однако я не понимаю, почему это так.Я могу понять, был ли алгоритм O(N), но я не знаю, откуда взялся logN в их анализе.

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

boolean isBalanced(TreeNode root) {
    if (root == null) return true; // Base case

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

Answer 1

getHeight определенно имеет линейную сложность.Он просто посещает каждый элемент в поддереве, поэтому O(k), где k - количество узлов в поддереве.

Теперь о isBalanced.Сначала он вычисляет высоту (которая является линейной, как мы видели ранее).Но тогда, если нам не так повезло, нам нужно вычислить isBalanced еще 2 раза: для левого и для правого поддеревьев.В худшем случае мы будем выполнять линейные вычисления для log N раз.

Вы можете изучить Основную теорему , которая описывает более общие случаи.

В этом конкретном случаепараметры для теоремы: a = b = 2 и при разделении задачи на подзадачи возникают постоянные накладные расходы.

Answer 2

Если мы сталкиваемся с несбалансированным узлом, мы получаем раннее возвращение false, так что это оптимальный случай. «Наихудший случай» для этого алгоритма - полностью сбалансированное дерево, поскольку мы не получаем ранних возвращений false. Для примера рассмотрим идеальное двоичное дерево с n узлами.

Первый вызов вызовет getHeight () на каждом узле, так что посещается n узлов. Общая работа для корневого уровня O (n).

Следующие два вызова (root.left.isBalanced () и root.right.isBalanced ()) вызовут getHeight () на последующих узлах, но каждый вызовет его только на ~ 1/2 n узлах. Общая работа для 1 высоты также O (n).

Следующие 4 вызова будут вызывать getHeight для n / 4 узлов каждый. Таким образом, общая работа для 2 высоты также O (n).

Если вы видите шаблон, общая работа для каждого уровня дерева равна O (n), поэтому общая работа для всех уровней составляет O (n) * уровней в идеальном дереве, которое выходит за O (nlogn) .

Answer 3

Наихудший вариант сложности этого алгоритма возникает в случае сбалансированного бинарного дерева поиска, так как в противном случае мы вернемся раньше.Рассмотрим следующее сбалансированное двоичное дерево поиска isBalanced Функция проходит по всем узлам один раз (включая нулевые дочерние элементы конечных узлов).Для каждого из этих узлов вызывается getHeight, чтобы вычислить высоту левого и правого дочернего элемента.Таким образом, getHeight требует работы, пропорциональной размеру поддерева, внедренного в этот узел.
Для нулевых потомков листьев (таких узлов 16) требуется постоянный объем работы.Для конечных узлов (1, 3, 5, 7...) нам нужно удвоить работу, но наш узел уменьшается вдвое (то есть у нас есть 8 узлов).На один уровень выше нам нужно в четыре раза больше работы, но наш узел снова делится пополам.
В общем, если у нас есть N узлов, таким образом, общий объем работы примерно равен

N + N/2*2 + N/4*4 + ... + N/N * 1

Каждый член суммы равенравно N.Сколько существует терминов?Это просто высота дерева, т.е. lg(N), так как мы уменьшаем N на 2, пока оно не достигнет 1.Таким образом, общая сложность составляет O(N*lg(N))

Answer 4

В формальном определении, если мы предположим, что сложность getHeight равна G(n), а T(n) - это сложность функции isBalance, у нас будет G(n) = G(n1) + G(n2) + 1 и T(n) = T(n1) + T(n2) + G(n) + 1 такой, что n1 будет размер левого поддерева, n2 - размер правого поддерева, n1 + n2 = n - 1.

Попробуйте расширить G(n) = (G(n11) + G(n12) + 1) + (G(n21)+G(n22) + 1) + 1, чтобы n11 + n12 + n21 + n22 = n1 - 1 + n2 - 1 = n - 3. Следовательно, G(n) = G(n11) + G(n12) + G(n21) + G(n22) + 3. Используя индукцию, мы можем найти, что G(n) = Theta(n). Поэтому у нас есть T(n) = T(n1) + T(n2) + \Theta(n) + 1.

Теперь, если высота разности поддеревьев больше 1, алгоритм вернет false и будет прерван, наихудший случай - |log(n2) - log(n1)| <= 1 (log(n{i}) - высота поддерева i). Следовательно, при включении питания 2 мы получаем n2/n1 <= 2. Это означает, что n1 и n2 являются постоянным фактором n, как у нас было n1 + n2 = n -1. Теперь из теоремы Акра-Бацци , p = 1 (приблизительно) и g(n) = n (как \Theta(n)) сложность T(n) в худшем случае составляет n*(1 + integral(x/x^2, 1, n)) = n*(1 + integral(1/x, 1, n) = n * (1 + log(n)). Следовательно, T(n) = O(n log(n)).