为什么Big O在这里没有为散列表定义？

Question

在此备忘单中，访问散列表的平均时间复杂度列为N/A。

我很好奇为什么。由于哈希表主要是数学外循环，我会假设它将O（1）像其他操作...搜索，插入，删除。

http://bigocheatsheet.com/

Answer 1

在该表中，“访问”列指的是时间访问一个给定的元件中，通过指数。这就是为什么在一个数组中，访问被描述为O（1） - 返回一个数组的第i个元素是一个常量时间操作。同样，对于一个链表，它是一个O（n）操作 - 如果你有一个链表，并且想要索引为i的项目，则需要从链接跳转到链接i次。

现在，在散列表（字典，散列表等）中，我们不谈论'索引i处的元素' - 我们根本不谈论索引！这就是这个表的意思是将NA作为哈希表的“访问”值。我们根本就没有（在这里使用的意义上）对hashmaps进行'访问'操作。

也许一个明确的例子可能会有所帮助。

myLinkedList = ['red','blue','orange']

myArray = ['black','white','green','yellow']

myHashMap = {'address':'10 wall st', 'gender':'male'}'

在头两个实施例中，我们可以访问给定的索引处的元素。

即：

myLinkedList[1] == 'blue'和

但我们可以通过索引不访问包含HashMap。

myHashMap[0]在这个实例中没有定义！因此，“访问”对于hashmaps来说是不适用的。

但是，在这种情况下，我们有相同的操作：按键搜索。

即：

myHashMap['address'] == '10 wall st'

的O（1）的操作。

无论你是否因为不知道数据结构内部结构而知道这个问题（在这种情况下，确实要学习它们，这是值得的），或者如果你仅仅被该表格上的术语所困惑，我希望这个答案能够帮助你。