algorithm - 嵌套循环解决方案的树遍历复杂度如何等于 O(n)

Question

当你遍历一棵树时，你可能只访​​问每个节点一次，逻辑上它的时间复杂度是 O(n)。但是如果你使用嵌套循环遍历(2、3 嵌套 for 循环)例如)为什么时间复杂度不是 O(n^2) 或 O(n^3)？我觉得它可能与边界有关，但是由于缺乏知识而不能确定。如果有人清楚地解释了这一点。

编辑:抱歉，我没有要显示的示例代码。正如下面的答案中所说，我实际上也不知道(也找不到任何示例代码。)，如何使用多个嵌套循环进行遍历。当我想到这个的时候，我的脑海里只是出现了一个假设问题。但是下面的答案很好地解决了我的困惑。

Answer 1

代码的复杂程度与您使用的数量 循环无关。这取决于这些循环到底在做什么。

如果你在你的树遍历代码中使用 2/3/4/n 循环，这样你只访问树中的每个节点一次，那么你的复杂度仍然是 O(n)，虽然我不是确定在这个特定示例中如何使用多个嵌套循环遍历一棵树。

但是，如果您有 2 个循环，这样对于第一个循环(树的每个节点)的每次迭代，您的第二个内部循环执行另一个树的完整遍历，那么您的复杂度将为 O(n^2 ).