data-structures - 平均时间为 O(1) 的 n 次操作是否平均每次都被视为 O(n)？

Question

我正在学习数据结构考试，我正在尝试解决这个问题：

给定一个包含 n 个数字和一个数字 Z 的数组，在 O(n) 平均时间内找到 x,y 例如 x+y=Z 。

我的建议是将数组的内容移动到哈希表中，并使用开放寻址执行以下操作：

对于每个数字 A[i] 在哈希表中搜索 ZA[i] （每个操作平均 O(1)。）最坏的情况下，您将执行 n 次搜索，每次 O(1) 平均时间，即 O(n ） 平均。

我的分析正确吗？

Answer 1

鉴于您第二次遍历所有数组，是的，这是 O(n) * O(1) （而不是我之前所说的 O(n)+O(1) ）（用于平均时间的哈希查找） ，所以你说的是 O(n) 复杂度的算法。