计算 On) 用于 hashmap 与二进制搜索

Question

我试图阐明如何计算以下情况的 O(n)：

给定一个排序数组，你如何在 O(n) 中找到两个总和等于给定数字 x 的数字？

O(n) 的解决方案是：

删除数组的第一个元素 (e0)
将其添加到哈希映射
删除数组的第一个元素 (e1)
目标是e1和x之间的差值
如果目标存在于散列映射中return 对
将 e1 添加到 hashmap
重复步骤 3-6，直到找到一对或运行个元素

这将是最坏的情况 O(n)，因为您只需要对数组进行一次传递。

O(n * log n) 的解决方案是：

从数组 (e1) 中删除第一个元素
目标是第一个元素与x的差值
二进制搜索数组的其余部分以获得目标
如果存在 return 对
重复步骤 1–4 直到找到一对或运行个元素

这是 O(n log n)，因为您需要运行二进制搜索 (log n) 最差 n/2 次给出 O(n/2 * log n)在大 O 中是 O(n * log n)

这是正确的吗？

Answer 1

这听起来像是您正在学习的某些课程中的家庭作业问题。我不会为你解决它——虽然很容易在网上找到解决方案——但我会告诉你，我 99% 确定你的解决方案必须花费 O(n) 时间，因为 worst-case 复杂度。 Hash-based 解决方案每次查找仅花费 O(1) 时间平均。

Answer 2

是的，对于这两种算法，您的分析都是正确的。

您的第一个算法也使用 O(n) space，因为 hashmap。你可以避免这种情况。

Algo : 
1. Consider begin = 0, and end = last_index
2. Consider data[begin] and data[end]
3. If data[begin] + data[end] > req_sum:
        end=end - 1  // u need to decrease ur total sum
   elif data[begin] + data[end] < req_sum:
        begin = begin + 1  // u need to increase ur total sum
   elif data[begin] + data[end] == req_sum:
          print("found")
4. Continue from Step 2.

显然避免 end < begin 和其他极端情况。

计算 On) 用于 hashmap 与二进制搜索

Calculating O(n) for a hasmap vs binary search

algorithm

hashmap

complexity-theory

binary-search

computation-theory