嵌套循环解决方案的树遍历复杂度如何等于 O(n)
How is nested loop solutions' complexity of tree treversal equals to O(n)
当你遍历一棵树时，你可能只访问每个节点一次，逻辑上它的时间复杂度是 O(n)。但是如果你使用嵌套循环遍历（2 , 3 nested例如 for 循环）为什么时间复杂度不是 O(n^2) 或 O(n^3)？我感觉它可能与边界有关，但是由于缺少 knowledge.I 无法确定如果有人清楚地解释这一点，我将不胜感激。
编辑：抱歉，我没有show.As在下面的答案中说的示例代码，我实际上也不知道（我也找不到任何示例代码。），如何遍历使用多重嵌套 loops.It 只是我在考虑 that.But 时脑海中出现的一个假设问题，下面的答案几乎满足了我的困惑。
您代码的复杂程度与您使用的数量 循环无关。这取决于这些循环到底在做什么。
如果你在你的树遍历代码中使用 2/3/4/n 循环，这样你只访问树中的每个节点一次，那么你的复杂度仍然是 O(n)，虽然我'我不确定在这个特定示例中如何使用多个嵌套循环遍历一棵树。
但是，如果您有 2 个循环，这样对于第一个循环（树的每个节点）的每次迭代，您的第二个内部循环执行树的另一个完整遍历，那么您的复杂度将是 O(n ^2).
当你遍历一棵树时，你可能只访问每个节点一次，逻辑上它的时间复杂度是 O(n)。但是如果你使用嵌套循环遍历（2 , 3 nested例如 for 循环）为什么时间复杂度不是 O(n^2) 或 O(n^3)？我感觉它可能与边界有关，但是由于缺少 knowledge.I 无法确定如果有人清楚地解释这一点，我将不胜感激。
编辑：抱歉，我没有show.As在下面的答案中说的示例代码，我实际上也不知道（我也找不到任何示例代码。），如何遍历使用多重嵌套 loops.It 只是我在考虑 that.But 时脑海中出现的一个假设问题，下面的答案几乎满足了我的困惑。
您代码的复杂程度与您使用的数量 循环无关。这取决于这些循环到底在做什么。
如果你在你的树遍历代码中使用 2/3/4/n 循环，这样你只访问树中的每个节点一次，那么你的复杂度仍然是 O(n)，虽然我'我不确定在这个特定示例中如何使用多个嵌套循环遍历一棵树。
但是，如果您有 2 个循环，这样对于第一个循环（树的每个节点）的每次迭代，您的第二个内部循环执行树的另一个完整遍历，那么您的复杂度将是 O(n ^2).