解释为什么这种二叉树遍历算法具有O（NlogN）时间复杂度？ [英] Explain why this binary tree traversal algorithm has O(NlogN) time complexity?

问题描述

我现在正在阅读《破解编码面试》一书，并且正在做二叉树练习。根据 O（NlogN）这本书有一段代码，但是，我不知道为什么。我可以理解算法是否为 O（N），但是我不知道 logN 的来源

I'm going through the Cracking the Coding Interview book right now and I'm doing a binary tree exercise. There is a snippet of code that is according to the book O(NlogN), however, I don't understand why that is. I can understand if the algorithm was O(N), but I don't know where the logN is coming from in their analysis.

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);
    }
}

推荐答案

如果我们遇到一个不平衡的节点，我们会早日返回false，因此这是最佳情况。该算法要处理的最坏情况是一棵完全平衡的树，因为我们没有得到false的早期返回。对于本示例，让我们使用一个具有n个节点的完美的二叉树。

If we encounter an unbalanced node, we get an early return of false so this is the optimal case. The "worst case" for this algorithm to handle is a completely balanced tree, since we get no early returns of false. For the sake of this example, let's use a perfect binary tree with n nodes.

第一个调用将触发每个节点上的getHeight（），因此访问了〜n个节点。根级别的总工作量为O（n）。

The first call would trigger getHeight() on each node so ~n nodes are visited. Total work for root level is O(n).

接下来的两个调用（root.left.isBalanced（）和root.right.isBalanced（））将触发getHeight （）在后续节点上，但每个节点仅在〜1/2 n个节点上调用它。 1个高度的总功也为O（n）。

The next two calls (root.left.isBalanced() and root.right.isBalanced()) would trigger getHeight() on subsequent nodes but each one only calls it on ~1/2 n nodes. Total work for 1 height is also O(n).

接下来的4个调用将分别在n / 4个节点上调用getHeight。因此，2个高度的总功也为O（n）。

The next 4 calls would call getHeight on n/4 nodes each. So total work for 2 height is also O(n).

如果看到该模式，则树的每个级别的总功为O（n），因此所有级别的总工作量为O（n）*完美树中的级别，得出O（nlogn）。

If you see the pattern, the total work for each level of the tree is O(n), so total work for all levels is O(n) * levels in a perfect tree, which comes out to O(nlogn).

这篇关于解释为什么这种二叉树遍历算法具有O（NlogN）时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！