在对计算算法运行时间的完全理论分析中； 如果我想在我的伪代码中包含一行涉及搜索数组中的值或给定键的哈希表的值，我应该假设此操作的运行时间是多少？例如，如果我之前存储了 A[3] = 6 并且我调用 A[3] 来检索 6，那么此操作的运行时间是否为 O(1)？或者它会被认为是使用某种最佳搜索算法的搜索操作并且是 O(log n)，其中 n 是 A 中的元素数？
最佳答案
假设我们谈论的是普通整数索引数组，存储在单个连续内存块中，对其进行索引通常是通过一次加法执行的，从而使访问恒定时间。
http://en.wikipedia.org/wiki/Array_data_structure#Efficiency
同样，哈希表通常提供常量时间访问，尽管该常量几乎可以保证比数组索引的常量大，因为哈希表更复杂并且通常构建在数组之上。合理的散列函数本身需要的远不止一次加法操作。
http://en.wikipedia.org/wiki/Hash_table#Performance_analysis
关于algorithm - 从数组或哈希表访问元素的运行时间是多少？它与查找或搜索有何不同？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16868988/