主页 / 问题 / 1242672
Accepted
Elizaveta
Asked:2022-02-11 16:31:58 +0000 UTC2022-02-11 16:31:58 +0000 UTC

算法复杂度估计

  • 772

假设我有一棵树。我的挑战是找到最深的叶子，因为它的根。这是伪代码：

heightFunc(elem)
   height = 1;
   for all children c in elem:
     height = max(height, 1 + heightFunc(c));
 return height;

很明显，他先把信息放到栈上，然后再取出来。但是这个算法的复杂度是多少？上）？O（登录）？你如何评价它？

алгоритм

1 个回答

  1. Best Answer

    该算法以线性时间 O(n) 运行。

    每个节点被访问一次，因为 树 - 节点只有一个父节点，我们不会两次去同一个节点

    树木是黑色和红色的，但仅此无济于事。但是如果节点存储了关于子树高度的附加信息（所谓的增广树（增补）），那么在O(1)中如果你在变化的过程中更新高度就可以找出树的高度结构（在平衡树的情况下以 O (logn) 为单位）

    • 4

相关问题