algorithm - 计算 HashMap 与二进制搜索的 O(n)

标签 algorithm hashmap complexity-theory binary-search computation-theory

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

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

O(n) 的解决方案是:

  1. 取出数组的第一个元素(e0)
  2. 将其添加到 HashMap 中
  3. 取出数组的第一个元素(e1)
  4. 目标是e1和x的差值
  5. 如果目标存在于散列映射中,则返回该对
  6. 将 e1 添加到 hashmap
  7. 重复步骤 3-6,直到找到一对或用完元素

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

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

  1. 从数组中取出第一个元素(e1)
  2. 目标是第一个元素与x的差值
  3. 二进制搜索数组的其余部分以找到目标
  4. 如果存在则返回对
  5. 重复步骤 1-4 直到找到一对或用完元素

这是 O(n log n),因为您需要在最坏情况下运行二分查找 (log n) n/2 次,给出 O(n/2 * log n),在大 O 中是 O(n * log n)

这是正确的吗?

最佳答案

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

您的第一个算法也使用 O(n) 空间,因为 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 的情况和其他极端情况。

关于algorithm - 计算 HashMap 与二进制搜索的 O(n),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42345198/

相关文章:

c++ - 比较两个无序集合的相等性有多昂贵?

c - 如果数字 <2^63,如何显示数字是否为质数?

javascript - 有人可以帮助我使用这种从某些值拆分数组的算法吗?

c - 将值插入双链表的中间

java - 根据我的顺序对 HashMap 进行排序

algorithm - T(n) = 2T(n/2) + log n 的解

algorithm - 从clrs书上看,插入排序for循环为什么要迭代n次?

java - 如何更改 HashMap 内的链接列表?

java - Big O中一般Hash表和java的HashMap的区别

c - 一个简单算法的时间复杂度