如何证明从最小节点在BST中找到n-1次后继者是O(n)?
问题是我们可以创建排序顺序
1)让节点= BST的最小节点。
2)从该节点,我们递归调用查找后继者。
有人告诉我结果为O(n),但我不明白,也不知道如何证明这一点。
应该不是O(n * log n)吗?因为对于第1步,它是O(log n),对于第2步,它也是O(log n),但被称为n-1次。因此,它将是O(n * log n)
请澄清我的疑问。谢谢!:)
您正确地认为任何单个操作都可能花费O(log n)的时间,因此,如果将这些操作执行n次,则应该获得O(n log n)的运行时间。这个界限是正确的,但并不严格。实际运行时间为Θ(n)。
一种查看方法是查看树中的任何单个边缘。如果从最左边的节点开始并重复执行后继查询,您将访问每个边缘多少次?如果仔细观察操作的工作方式,您会发现每个边缘都被精确地访问了两次:一次向下和一次向上。由于完成的所有工作都是沿上下边缘进行的,因此这意味着完成的工作总量与边缘数量的两倍成正比。在任何树中,边数是节点数减一,因此完成的总功为Θ(n)。
为了对此进行形式化证明,请尝试显示您从未两次下降相同的边缘,而当您上升一条边缘时,您再也不会下降了该边缘。完成上述操作后,可以从上述逻辑得出运行时间为Θ(n)的结论。
希望这可以帮助!
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句