让我们考虑以下代码。我试图创建一个结果向量，它包含一个单独的内部向量中n元树的每一级。以下代码的时间复杂度是多少？
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
queue<Node*>q;
q.push(root);
vector<vector<int>> v; //Resultant vector
vector<int> inn; //inner vector
if(!root){
return v;
}
inn.push_back(root->val);
while(!q.empty()){
int qn=q.size();
v.push_back(inn);
inn.clear();
for(int i=0;i<qn;i++){
Node* cur=q.front();
if((cur->children).size()){
for(auto child:cur->children){
q.push(child);
inn.push_back(child->val);
}
}
q.pop();
}
}
return v;
}
};
在多个嵌套循环的情况下，我们如何将时间复杂性评估为O(N(？这里N是树中节点的数量。
时间复杂度实际上是O(N(。有嵌套循环的代码不可能具有这样的时间复杂性，这是没有规律的。
考虑每个节点都被添加一次到队列q，并且被从队列q移除一次。
尽管最内部的for循环看起来可能会使时间复杂性非线性，但事实并非如此：该循环的一次迭代将始终处理不同的child节点，我们知道其中只有N个。
我们还可以观察到，最内部的for循环通常根本不迭代。树上的叶子就是这样。这可能有助于直观地接受这确实是一种具有线性时间复杂性的算法。