数据结构 - 访问和索引的大 O。它们的真正含义是什么？

Question

我在网上找了两篇文章：

第一的

第二

让我感到困惑的是他们使用的术语索引和访问。他们指的是同一件事吗？

以数组为例：

第一个说访问的大 O 是 O(1)。第二个说索引的大 O 是 O(1)。所以我假设他们都说给定一个索引x，你可以得到array[x]O(1) 中的值。

以哈希表为例：

第一个说 Big O of Access 是 N/A。我认为这是因为使用哈希表，您只能通过键进行搜索。您不会通过索引检索值。但是第二个说索引的大 O 是 O(1)。也许这次是指搜索？

现在以二叉树为例：

第一个：访问是 O(logN)。第二个：索引是 O(logN)。

什么？

所以现在他们都指的是搜索？您不能通过索引从二叉树中检索值，对吗？

请帮我澄清一下。谢谢！

Answer 1

在上面的文章中，索引和访问意味着同一件事，它们都描述了访问元素所需的渐近复杂性。

进一步来说：

• 在数组中，当谈论访问例如第三个元素时，索引或访问当然是 O(1) ，而由于最坏情况下需要线性传递，搜索是 O(n) 。
• 在哈希表中，很明显我们不能引用索引，例如第三个元素是什么 - 这个问题没有意义。考虑到上述通知，第一篇文章表示不适用。第二篇文章认为哈希表 - 索引是查找一个元素（您知道该元素的哈希键）。那么，如果你有一个好的哈希表（好的长度和最重要的好的哈希函数），那么找到一个元素确实是几乎恒定的时间 O(1)。
• 在二叉树中查找 - 搜索元素的时间复杂度为 O(logn)。在这里，第一篇文章使用“访问”一词，指的是搜索元素，正如您已经指出的那样。您无法通过索引从二叉树中检索值，但第二篇文章通过索引它意味着搜索，因为在其他情况下索引没有任何意义。请注意，在二叉搜索树中搜索（或访问或索引或搜索）不是 O(logn) 而是 O(n)，因为想象一下我们在树中插入排序元素的情况（例如 1,2,3,4,5， ...）然后树就变成了一个列表并且搜索是线性的。很多时候，它被称为 O(logn)，因为元素排序的情况很少见，大多数时候它需要 O(logn)（但这是平均情况的渐近复杂度，而不是最坏的！）。如果您使用 AVL 树，其中树始终是平衡的并且搜索时间为 O(logn)，那么您将获得 O(logn)。

因此，在上述文章中的哈希表和二叉搜索树中，访问索引被称为搜索。