gpt4 book ai didi

java - 无法理解 TreeNode 中的 Big-O

转载 作者:行者123 更新时间:2023-11-30 09:09:44 27 4
gpt4 key购买 nike

我无法理解大 O 问题。

问题

public boolean isHB(TreeNode root){
if (root==null)
return tree;
int heightL = height(root.left);
int heightR = height(root.right);
boolean leftHB = isHB(root.left);
boolean rightHB = isHB(root.right);
if (Math.abs(heightL-heightR)>1)
return false;
return leftHB && rightHB;
}

1/假设树是高度平衡的。找到大 O,其中 n 是树中的节点数。

2/不要假设树是高度平衡的。找到大 O,其中 n 是树中的节点数。

我不明白的地方

1/解是:2T(2/n) + O(n) = O(n log(n))。我知道 2T(2/n) 的来源,但我不知道 O(n) 的来源。

2/解是:T(n-1) + O(n) = O(n^2)。在这种情况下,由于树不平衡,我理解 T(n-1),但我仍然无法弄清楚 O(n) 从何而来。

最佳答案

求一棵树的高度复杂度为 O(n)。所以额外的部分是找到高度的复杂性。

关于java - 无法理解 TreeNode 中的 Big-O,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22927321/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com