显示泛型树并查找其中节点总数的时间复杂度

Question

我在理解显示泛型树和查找其中节点总数的时间复杂性方面遇到了一些困难。我已经在网上寻找了一些文章，有关于什么是泛型树的文章，但没有太多关于泛型树的时间复杂性。我之前认为它将是O(N)用于查找节点总数，O(N)用于显示所有节点(显示节点的数据)，但在我学习泛型树的视频中有一条评论说，它O(N)用于显示树的所有节点，O(N^N)用于查找其中的节点总数，其中'N‘是节点总数。有人能帮帮我吗？

Answer 1

无论采用深度优先还是广度优先的方法，访问有限泛型树的所有节点都是O(N)。因此，计算节点的数量也是O(N)，如果计数存储在节点中，则为O(1)。

仅当打印单个节点是O(1)时，打印所有节点才是O(N)。通常情况并非如此。例如，如果树的N个节点包含数字1...N，则打印节点值(二进制或十进制)的复杂度将为O(N log N)。