我看到过关于 GeeksforGeeks 挑战解决方案的最坏情况时间复杂度的相互矛盾的说法，：
给定两棵二叉树。检查它们是否同构。
笔记：
如果一棵树可以通过一系列翻转从另一棵树获得，即通过交换多个节点的左子节点和右子节点，则两棵树被称为同构树。任何级别的任何数量的节点都可以交换其子节点。两棵空树是同构的。
例如，以下两棵树是同构的，并且以下子树被翻转：2 和 3、NULL 和 6、7 和 8。
我的问题涉及以下解决这个问题的算法：
isomorphic(Node root1, Node root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
if (root1.data != root2.data) {
return false;
}
return (isIsomorphic(root1.left, root2.left) &&
isIsomorphic(root1.right, root2.right)) ||
(isIsomorphic(root1.left, root2.right) &&
isIsomorphic(root1.right, root2.left));
}
本次代码挑战附带的社论介绍了此算法并指出：
时间复杂度： O(min(N1, N2))，其中 N1 和 N2 是两棵树中的节点数。该算法仅遍历每棵树的节点，直到较小的树结束为止。这是因为如果较小的树结束，较大的树中的额外节点将不会在较小的树中有对应的节点，从而使树变得不同构。因此，该算法的时间复杂度取决于两棵树中较小的一棵树中的节点数，用 min(N1, N2) 表示。
Gevendra Verma 在评论区中也发表了一篇排名靠前且被置顶的文章，文中也阐述了同样的算法：
该算法的时间复杂度为 O(n)，其中 n 是树中的节点数。这是因为我们只访问每个节点一次。
然而，其他一些人在评论部分声称它不是线性的，使用以下逻辑：
假设我们有 L 个级别，标记为 l 到 0，其中 0 是最低级别。现在，T(l) = 4 T(l-1)+c（为简单起见，将所有 4 次递归检查视为同时进行）T(l) = 4^L + c (4+4^2+4^3+….+4^(l-1)) T(l) = 4^L+c*4^L
T(L) = c*4^L
现在，L 是 logN，对吗？因此，T(L) = c*4^LogN
O（N）= 2^2*LogN = N^2
但许多其他资料声称时间复杂度是线性的。那么谁是对的呢？反驳的论点是这样的：
要么调用节点的左侧和右侧，如果结果为 true，则不再调用节点的左侧和右侧。如果在第一种情况下结果为 false，则所选节点将不再进行进一步调用，您将调用第二个右侧和左侧
我认为，也许由于我们在每个级别进行了 2 次比较，所以我们总共进行了 2小时的比较。因此 2 log(n) = n。
这个特定算法的真实时间复杂度是多少？谁是这里的正确人选？
8
最佳答案
1
它不是线性的。我还没有绝对的证据（目前），但我认为有足够多的证据表明，在最坏的情况下它是 O(𝑛log𝑛)，所以我决定发布我所拥有的：
对所提主张的第一印象
您为捍卫 O(𝑛) 复杂度所做的引述是：
要么调用节点的左侧和右侧，如果结果为 true，则不再调用节点的左侧和右侧。如果在第一种情况下结果为 false，则所选节点将不再进行进一步调用，您将调用第二个右侧和左侧
但这不是正确的推理。对于给定的函数执行，这不是基本情况，第一次递归调用是：isIsomorphic(root1.left, root2.left)。现在让我们关注root1.left：在第一次调用返回之前，可能会对该子树进行大量遍历。如果返回 false，isIsomorphic(root1.left, root2.right)则调用。请注意，我们可能会root1.left 再次遍历很大一部分！现在，如果在该遍历的任何地方我们重复了这种情况，就会产生指数效应：对相同节点的 2 次遍历变成 4 次，……等等。
其次，如果我们简单地在树的每个节点上放置一个计数器属性，并为作为函数第一个参数的节点增加它，我们可以快速看到这些计数可以（远）高于 1 或 2。
但是那些反驳它并说它是 O(𝑛²)（如您所引用）的人也是错误的：在每次评估布尔表达式（使用递归调用）时，我们都可以进行 4 次递归调用的说法是行不通的：如果您有 4 次递归调用，那么从逻辑上讲结果将为 false（只需考虑一下），但如果所有 4 个“子代”也最大化其递归调用的数量，那么这些也都会返回 false，这会导致矛盾，因为您需要两个递归调用返回 true，另外两个返回 false。因此，一般来说，不可能总是达到 4 次调用的最大值。
最坏的情况
为了分析复杂性，我们需要了解就 𝑛 而言什么构成了最坏的情况：
- 我们应该保持所有内部节点的值相等，这样递归树就不会仅仅因为内部节点中的数据而被切断。
- 两棵树的形状可以相同，并且为了在交换左、右角色时也保持它们相同，我们增加了递归的潜在深度，因此我们得到了完美的二叉树（其中所有内部节点都有两个子节点并且所有叶子都在同一级别）。
- 为了最大化调用次数，我们需要函数有时返回 false，有时返回 true：（短路）逻辑 OR 仅在第一个操作数为 false 时才计算第二个操作数，而（短路）逻辑 AND 仅在第一个操作数为 true 时才计算第二个操作数。因此，我们需要一些在两棵树中都不相同的值。
经过几个小时的随机样本测试，我发现以下树配置针对 𝑛 产生的调用次数最多。
树中的所有值都应该相同（我选择了 0），除了 5 个值（我选择了 1）。如果我们将两棵树的底层分成 4 个相等的组（从左到右），那么这些 1 值应该位于此处：
Left tree: 00...01 00...00 00...01 00...01
Right tree: 00...00 10...00 00...00 10...00
例如，如果选定的高度是 3（最长根叶路径上的边数），则 𝑛 = 15，我们得到以下输入：
____0____ ____0____
/ \ / \
_0_ _0_ _0_ _0_
/ \ / \ / \ / \
0 0 0 0 0 0 0 0
/ \ / \ / \ / \ / \ / \ / \ / \
0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0
计数呼叫
我决定计算那些没有参数的调用null，并使用这个函数扩展（在 JavaScript 中）：
function countIsomorphic(root1, root2) {
let count = 0; // To be returned
// Your function:
function isomorphic(root1, root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
count++; // Added
if (root1.data != root2.data) {
return false;
}
return (isomorphic(root1.left, root2.left) &&
isomorphic(root1.right, root2.right)) ||
(isomorphic(root1.left, root2.right) &&
isomorphic(root1.right, root2.left));
}
// Call the function
isomorphic(root1, root2);
return count; // Ignore the boolean result, but return the count instead
}
经过几个小时的数字分析后，我终于countIsomorphic根据输入树（两棵）的高度ℎ得出了返回值的公式：
（2ℎ−3）2ℎ +1 +9
注意：我只能通过经验发现这一点，所以我必须说这不是一个证据。
由于 𝑛 = 2 ℎ+1 − 1，因此 ℎ = log 2 (𝑛 + 1) − 1，这意味着我们的通话次数为
(2log 2 (𝑛 + 1) − 5)(𝑛 + 1) + 9
…这意味着最坏情况的时间复杂度是 O(𝑛log𝑛)。
说明公式
下面是一个可运行的代码片段（JavaScript 代码），它计算高度在 1 到 14 之间的调用次数，并将此计数与上述公式得出的结果进行比较。它们是相等的，因此我非常有信心，对于更高高度的树（具有我之前描述的形状/图案），这也是正确的：
class Node {
constructor(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
}
function countIsomorphic(root1, root2) {
let count = 0; // To be returned
// Your function:
function isomorphic(root1, root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
count++; // Added
if (root1.data != root2.data) {
return false;
}
return (isomorphic(root1.left, root2.left) &&
isomorphic(root1.right, root2.right)) ||
(isomorphic(root1.left, root2.right) &&
isomorphic(root1.right, root2.left));
}
// Call the function
isomorphic(root1, root2);
return count; // Ignore the boolean result, but return the count instead
}
function makePerfectTree(binary) {
let level = Array.from(binary, digit => new Node(digit));
while (level.length > 1) {
level.push(new Node(0, ...level.splice(0, 2)));
}
return level.pop();
}
function getCount(h) {
const length = 1 << h;
const binary1 = Array(length).fill(0);
const binary2 = Array(length).fill(0);
// Create (apparent) worst case pattern:
const quarter = 1 << (h-2);
const mid = 1 << (h-1);
binary1[quarter - 1] = 1;
binary2[quarter] = 1;
binary1[mid + quarter - 1] = 1;
binary2[mid + quarter] = 1;
binary1[length-1] = 1;
// Create two perfect trees of given height, and populate the
// leaf-level with the given values
const root1 = makePerfectTree(binary1);
const root2 = makePerfectTree(binary2);
// Run the algorithm to get back a call-count
return countIsomorphic(root1, root2);
}
for (let h = 1; h <= 14; h++) {
const actual = getCount(h);
const calculated = (2*h-3) * 2**(h+1) + 9;
console.log(`for height ${h}, the call count is ${actual}`);
if (actual !== calculated) throw `Got ${actual}, but calculated ${calculated}!`
}
|
–
–
–
–
–
|