图中层序遍历的时间复杂度

Question

时间复杂度：O(n) 谁能在数学上将时间复杂度解释为 O(n)。我可以发现 while 循环是 O(logn)

public:
    vector<vector<int>> levelOrder(Node* root) {
        if(!root) return vector<vector<int>>{};
        queue<Node*> q;
        q.push(root);
        vector<vector<int>> res;
        
        while(!q.empty()){
            //BFS traversal
            int size= q.size();
            vector<int> level;
            
            for(int i= 0; i< size; i++){
                auto tmp= q.front(); q.pop();
                level.push_back(tmp->val);
                for(auto n: tmp->children)
                    q.push(n);
            }
            res.push_back(level);
        }
        return res;
    }
}

Answer 1

好吧，你只访问每个节点一次，所以这里的复杂度是 O(n)。这个问题不是“分而治之”的算法，因为你最终会访问一个节点的所有分支（在二分法算法中，你只访问一个分支）。

编辑

递归算法的复杂性可能非常棘手。这个公式可以帮助你：当你有 T(n) 你的时间复杂度时，

T(n) = aT(n/b) + f(n).

如果f(n) = Θ(n^d)，其中d≥0，则

T(n) = Θ(n^d) 如果 a < b^d
T(n) = Θ(n^d*log(n)) 如果 a = b^d
T(n) = Θ(n^log_b(a)) 如果 a > b^d

在你的例子中，f(n) = Θ(1)，因为你在一个节点什么都不做，所以d=0。你一般也有a=b>1，所以你属于第三种情况。 Log_b(a) = 1，因为b=a，所以你的复杂度是Θ(n¹).

图中层序遍历的时间复杂度

Time complexity of level order traversal in graph

graph

tree

time-complexity

binary-tree

space-complexity