algorithm - 从数组或哈希表中访问元素的运行时间是什么？它与查找或搜索有何不同？

Question

对计算算法运行时间进行完全理论分析；如果我想在我的伪代码中包含一行，涉及在给定键的情况下搜索数组中的值或哈希表的值，我应该假设此操作的运行时间是多少？例如，如果我之前存储了 A[3] = 6，并且我调用 A[3] 来检索 6，那么这个操作的运行时间是 O(1) 吗？或者它是否会被认为是使用某种最佳搜索算法的搜索操作，并且是 O(log n)，其中 n 是 A 中的元素数？

Answer 1

假设我们谈论的是一个普通的整数索引数组，存储在一个连续的内存中，对它的索引通常通过一次加法来执行，从而使访问时间恒定。

http://en.wikipedia.org/wiki/Array_data_structure#Efficiency

同样，哈希表通常提供常量时间访问，尽管该常量几乎可以保证大于数组索引的常量，因为哈希表更复杂并且通常构建在数组之上。仅合理的散列函数就需要远不止一个加法操作。

http://en.wikipedia.org/wiki/Hash_table#Performance_analysis

Answer 2

从散列中检索一个值在最坏的情况下是线性时间（意味着每个键散列到相同值的情况），但它的平均情况是常数时间。如果您正在处理实时系统，那么您需要将其视为 O(n)，但通常您可以将其视为 O(1)。

Answer 3

如果 A[3] = 6; 你想得到 A[3] 然后它是一个 O(1) 步骤，因为数组为每个元素分配内存。假设 A 是一个 int 数组，第 0 个元素的位置是 x 因此 java 直接转到该地址并在恒定时间内获取相应的元素。
location of 1st element is x+4 (considering int to be 4 bytes)
location of 2nd element is x+8
location of 3rd element is x+12 ... Like wise all element.
so location of ith element is x+4*i;