c++ - 将树节点添加到向量向量中的 n 元树遍历的平均和最坏情况时间复杂度是多少？

Question

我正在努力理解这个算法的时间复杂度。给定一个像这样的 n 叉树遍历算法：

std::vector<std::vector<int>> levelOrder(Node* root) {
  std::queue<Node*> queued_nodes;
  std::vector<std::vector<int>> return_vector;
  if (!root) {
    return return_vector;
  }
  queued_nodes.push(root);
  queued_nodes.push(nullptr);
  std::vector<int> current_vector;
  while (!queued_nodes.empty()) {
    Node* current_node = queued_nodes.front();
    queued_nodes.pop();
    if (current_node) {
      current_vector.push_back(current_node->val);
      for (Node* child : current_node->children) {
        queued_nodes.push(child);
      }
    } else {
      if (!queued_nodes.empty()) {
        queued_nodes.push(nullptr);
      }
      if (current_vector.size()) {
        return_vector.push_back(current_vector);
        current_vector.clear();
      }
    }
  }
  return return_vector;
}

上述算法在树上进行广度优先搜索。current_vector存储在树的当前级别上找到的节点向量。return_vector存储树中每个级别的向量向量。每当我们从队列中遇到一个新节点时，我们push_back()将节点指向current_vector，如果我们开始探索树中的新级别，我们push_back()将current_vector指向return_vector然后清除current_vector。

1）我知道图上的深度优先搜索的时间复杂度为 O(V + E)，而在二叉树上，由于边的数量是节点数的两倍，我们可以将其推广到 O(V)。但是，我们可以在这里对 n 叉树做出相同的假设吗？

2) 我知道 的时间复杂度push_back()是一个摊销常数，但我们至少在做 |V| 次（Node*树中的每个一次）。那么push_back()a Node*tocurrent_vector和push_back()of acurrent_vector将如何return_vector影响整个算法的时间复杂度呢？

谁能告诉我他们将如何分析这种算法的复杂性？

标签： c++time-complexity

Answer 1

1) 一棵树的边数总是V-1。您可以通过将每个边缘远离根部来看到这一点。然后每个节点都只有一个传入边，除了根，它没有。

如果V只计算非叶节点，这当然不再正确。那么我们可以说边的数量最多是内部节点所有度数的总和，因为每条边都至少与一个内部节点相关。（实际上，我们知道2E = sum of degrees + number of leafs，但这在这里并不重要）。因此，对于 n 叉树，我们有E <= N * V因为 N 叉树中每个内部节点的度数（最多）为 N。

因此 dfs 的运行时间是O( V + N * V) = O(V)因为 N 是常数。

2)每个节点调用一次push_back。oncurrent_vector每层调用一次，也可以以 V 为界。由于该方法的摊销运行时间是常数，因此所有这些操作的摊销运行时间为。push_backreturn_vectorO(V)

push_back复制有一个问题current_vector，所以它的每个元素都被再次查看和复制。但是对于树的每个节点，这仅执行一次，因此在O(V).

所以影响是运行时间估计不再摊销了。

关于更实际的性能方面：您应该current_vector将return_vector. 这具有恒定的运行时间，并且与副本的元素数量不成线性关系。