通常，如果使用深度优先遍历，我们会得到O(n)时间。但是，如果我们先找到最小元素，然后调用successor()方法n次数，它的时间复杂度是多少？
我认为这可能是O(n log n)因为继任者是O(log n)，但这似乎不对。谁能在这里提供任何深入的分析（可能涉及一些极限分析）？
问问题
4158 次
2 回答
8
如果每个节点都存在父指针，则调用后继方法 n 次需要 O(n) 时间。为了看到这一点，观察到树中的每条边最多被所有后继调用组合访问两次（一次从父到子，一次从子到父）。因此，所有后继调用访问的边总数最多为 2n。所以运行时间是O(n)。
现在，如果不存在父指针，则在每次调用中，我们都必须从根开始并通过 O(log n) 个节点搜索后继元素（如果树是平衡的）。因此复杂度变为 O(n log n)。
于 2012-09-16T20:20:33.780 回答
0
不是一个正式的论点，但对于 O(n) 来说是一个相当有说服力的论点：
后继函数总是采用从起始节点到其后继节点的最短路径。它要么下降，要么上升，但一旦开始做一个，就不能改变另一个。因此，它必须采取最短路径。
后继函数必须产生与深度优先方法相同的输出，因此它必须以相同的顺序访问相同的节点（即输出的节点，它不必经过相同的节点，尽管它确实如此） .
深度优先方法也总是采用每个输出节点之间的最短路径（在每一步中它要么向下要么向上，而不是两者）。
因此，每种方法都采用完全相同的路径，实际上是等价的。
于 2012-09-16T14:23:28.073 回答