如何证明从最小节点在BST中找到n-1次后继者是O(n)?

拉贝斯

如何证明从最小节点在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)

请澄清我的疑问。谢谢!:)

templatetypedef

您正确地认为任何单个操作都可能花费O(log n)的时间,因此,如果将这些操作执行n次,则应该获得O(n log n)的运行时间。这个界限是正确的,但并不严格实际运行时间为Θ(n)。

一种查看方法是查看树中的任何单个边缘。如果从最左边的节点开始并重复执行后继查询,您将访问每个边缘多少次?如果仔细观察操作的工作方式,您会发现每个边缘都被精确地访问了两次:一次向下和一次向上。由于完成的所有工作都是沿上下边缘进行的,因此这意味着完成的工作总量与边缘数量的两倍成正比。在任何树中,边数是节点数减一,因此完成的总功为Θ(n)。

为了对此进行形式化证明,请尝试显示您从未两次下降相同的边缘,而当您上升一条边缘时,您再也不会下降了该边缘。完成上述操作后,可以从上述逻辑得出运行时间为Θ(n)的结论。

希望这可以帮助!

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

bst中连续k次调用树后继者

来自分类Dev

如何在O(n)中的列表列表中找到最小正整数?

来自分类Dev

在O(log n)中找到第k个最小元素

来自分类Dev

如何在二维numpy矩阵中找到前n个最小值

来自分类Dev

如何在Pandas Dataframe中找到n行数据的最小或最大列?

来自分类Dev

在3维矩阵(或n维)中找到最小元素的索引

来自分类Dev

在3维矩阵(或n维)中找到最小元素的索引

来自分类Dev

pygraphviz:使用后继者找到最大秩节点

来自分类Dev

如何在O(n)时间和O(n)空间中找到重复大小为n的数组的(n / 3)次重复的数字?

来自分类Dev

此递归二进制搜索如何工作?用于在bst中找到第k个最小的节点

来自分类Dev

搜索BST节点的后继者,“克隆以满足借用检查器”灾难

来自分类Dev

给定一棵树,在Log(n)中找到从节点“ a”到节点“ b”的路径中的第k个节点?

来自分类Dev

考虑到数组未排序且 n 是数组的大小,如何在 nk 个比较中找到 k 个最小元素之一

来自分类Dev

如何从n个元素中找到k个置换的索引?

来自分类Dev

如何从数组中找到第n个重复项

来自分类Dev

如何在Prolog中找到列表的第N个元素

来自分类Dev

如何在递归中找到T(n)的渐近上限?

来自分类Dev

如何在XTS中找到第N行的索引

来自分类Dev

如何从数组中找到第n个重复项

来自分类Dev

如何从n个元素中找到k个置换的索引?

来自分类Dev

如何在javascript中找到第n个位置tagName

来自分类Dev

如何在Notepad ++中找到第N个字符?

来自分类Dev

如何在递归中找到T(n)的渐近上限?

来自分类Dev

jquery如何从元素变量中找到第n个孩子

来自分类Dev

你如何在python中找到前N个素数?

来自分类Dev

如何从 kNeighborsClassifier 中找到前 n 个匹配项?

来自分类Dev

如何在列表中找到小于 n 的 2 的最高幂?

来自分类Dev

从n个np.array中找到m个“最小”元素

来自分类Dev

在n个可能的不同位置中找到k个对象之间的最大最小距离?

Related 相关文章

  1. 1

    bst中连续k次调用树后继者

  2. 2

    如何在O(n)中的列表列表中找到最小正整数?

  3. 3

    在O(log n)中找到第k个最小元素

  4. 4

    如何在二维numpy矩阵中找到前n个最小值

  5. 5

    如何在Pandas Dataframe中找到n行数据的最小或最大列?

  6. 6

    在3维矩阵(或n维)中找到最小元素的索引

  7. 7

    在3维矩阵(或n维)中找到最小元素的索引

  8. 8

    pygraphviz:使用后继者找到最大秩节点

  9. 9

    如何在O(n)时间和O(n)空间中找到重复大小为n的数组的(n / 3)次重复的数字?

  10. 10

    此递归二进制搜索如何工作?用于在bst中找到第k个最小的节点

  11. 11

    搜索BST节点的后继者,“克隆以满足借用检查器”灾难

  12. 12

    给定一棵树,在Log(n)中找到从节点“ a”到节点“ b”的路径中的第k个节点?

  13. 13

    考虑到数组未排序且 n 是数组的大小,如何在 nk 个比较中找到 k 个最小元素之一

  14. 14

    如何从n个元素中找到k个置换的索引?

  15. 15

    如何从数组中找到第n个重复项

  16. 16

    如何在Prolog中找到列表的第N个元素

  17. 17

    如何在递归中找到T(n)的渐近上限?

  18. 18

    如何在XTS中找到第N行的索引

  19. 19

    如何从数组中找到第n个重复项

  20. 20

    如何从n个元素中找到k个置换的索引?

  21. 21

    如何在javascript中找到第n个位置tagName

  22. 22

    如何在Notepad ++中找到第N个字符?

  23. 23

    如何在递归中找到T(n)的渐近上限?

  24. 24

    jquery如何从元素变量中找到第n个孩子

  25. 25

    你如何在python中找到前N个素数?

  26. 26

    如何从 kNeighborsClassifier 中找到前 n 个匹配项?

  27. 27

    如何在列表中找到小于 n 的 2 的最高幂?

  28. 28

    从n个np.array中找到m个“最小”元素

  29. 29

    在n个可能的不同位置中找到k个对象之间的最大最小距离?

热门标签

归档