数据结构 - 访问和索引的大 O。他们到底是什么意思？
Data structure - Big O of access and indexing. What do they really mean?
网上找了两篇文章：
让我感到困惑的是他们使用的术语 Indexing 和 Access。他们指的是同一件事吗？
以数组为例：
第一个说Access的Big O是O(1)。第二个说索引的大 O 是 O(1)。所以我假设他们都说给定一个索引 x，你可以在 O(1).
中得到 array[x] 的值
以哈希Table为例：
先说Access的大O是N/A。我认为这是因为使用哈希 Table，您只能通过一个键进行 搜索 。您不会通过索引检索值。但是第二个说索引的大 O 是 O(1)。这次可能是指搜索？
现以二叉树为例：
第一：访问是O(logN)。第二：索引是O(logN).
什么？
所以现在他们都指的是搜索？您不能通过索引从二叉树中检索值，对吗？
请帮我澄清一下。谢谢！
在上面的文章中，索引和访问是同一回事，它们都描述了访问元素所需的渐近复杂性。
更具体地说：
- 在数组中，索引或访问当然是 O(1) 时谈论
访问例如第三个元素，搜索是 O(n) 由于
最坏情况下需要线性传递。
- 在 Hashtables 中明确指出我们不能引用索引，例如
第三个元素是什么——这个问题毫无意义。第一篇
说 N/A 考虑到上述通知。第二
文章认为 Hashtable - 索引是寻找一个元素
（您知道元素的哈希键）。那么这是真的
如果你有一个好的哈希表（长度和
最重要的好散列函数）它几乎是常数时间 O(1).
- 在二叉树中查找 - 搜索元素是 O(logn)。这里的
第一篇文章使用访问这个词，指的是搜索
你已经很好地指出了这一点。你无法检索
通过索引从二叉树中获取值，但通过索引获取第二篇文章
这意味着搜索，因为在其他情况下索引并不意味着
任何事物。请注意，搜索（或访问或索引或
在二叉搜索树中搜索）不是 O(logn) 而是 O(n) 因为
想象一下我们在树中插入排序元素的情况（例如
1,2,3,4,5,...) 然后树变成一个列表并且搜索是线性的。
很多时候它被称为 O(logn) 因为在这种情况下
对元素进行排序的情况很少见，而且大多数时候都需要
O(logn)（但这是平均情况的渐近复杂性，而不是
最坏！ ).如果你使用 AVL 树，你会得到 O(logn)
树总是平衡的，搜索是 O(logn)。
因此在上述文章中的哈希表和二叉搜索树中，访问索引被称为搜索。
网上找了两篇文章：
让我感到困惑的是他们使用的术语 Indexing 和 Access。他们指的是同一件事吗？
以数组为例：
第一个说Access的Big O是O(1)。第二个说索引的大 O 是 O(1)。所以我假设他们都说给定一个索引 x，你可以在 O(1).
array[x] 的值
以哈希Table为例：
先说Access的大O是N/A。我认为这是因为使用哈希 Table，您只能通过一个键进行 搜索 。您不会通过索引检索值。但是第二个说索引的大 O 是 O(1)。这次可能是指搜索？
现以二叉树为例：
第一：访问是O(logN)。第二：索引是O(logN).
什么？
所以现在他们都指的是搜索？您不能通过索引从二叉树中检索值，对吗？
请帮我澄清一下。谢谢！
在上面的文章中，索引和访问是同一回事，它们都描述了访问元素所需的渐近复杂性。
更具体地说：
- 在数组中，索引或访问当然是 O(1) 时谈论 访问例如第三个元素，搜索是 O(n) 由于 最坏情况下需要线性传递。
- 在 Hashtables 中明确指出我们不能引用索引，例如 第三个元素是什么——这个问题毫无意义。第一篇 说 N/A 考虑到上述通知。第二 文章认为 Hashtable - 索引是寻找一个元素 （您知道元素的哈希键）。那么这是真的 如果你有一个好的哈希表（长度和 最重要的好散列函数）它几乎是常数时间 O(1).
- 在二叉树中查找 - 搜索元素是 O(logn)。这里的 第一篇文章使用访问这个词，指的是搜索 你已经很好地指出了这一点。你无法检索 通过索引从二叉树中获取值，但通过索引获取第二篇文章 这意味着搜索，因为在其他情况下索引并不意味着 任何事物。请注意，搜索（或访问或索引或 在二叉搜索树中搜索）不是 O(logn) 而是 O(n) 因为 想象一下我们在树中插入排序元素的情况（例如 1,2,3,4,5,...) 然后树变成一个列表并且搜索是线性的。 很多时候它被称为 O(logn) 因为在这种情况下 对元素进行排序的情况很少见，而且大多数时候都需要 O(logn)（但这是平均情况的渐近复杂性，而不是 最坏！ ).如果你使用 AVL 树，你会得到 O(logn) 树总是平衡的，搜索是 O(logn)。
因此在上述文章中的哈希表和二叉搜索树中，访问索引被称为搜索。