计算hasmap与二进制搜索的O(n)
计算hasmap与二进制搜索的O(n)
提问于 2017-02-20 12:57:22
我试图澄清如何计算以下情况的O(n)：
给定一个排序数组，如何在O(n)中找到其和等于给定数字x的两个数字？
O(n)的解决办法是：
- 删除数组的第一个元素(e0)
- 将此添加到hashmap中
- 删除数组的第一个元素(e1)
- 目标是e1和x的区别
- 如果目标存在于散列映射中，则返回对
- 将e1添加到hashmap
- 重复步骤3-6，直到找到一对或用完元素为止。
这将是最糟糕的情况O(n)，因为您只需要对数组进行一次传递。
O(n * log n)解决方案是：
- 从数组(e1)中删除第一个元素
- 目标是第一个元素与x之间的区别。
- 二进制搜索数组的其余部分以寻找目标。
- 如果存在，则返回对
- 重复步骤1-4，直到找到一对或用完元素为止。
这是O(n log )，因为您需要在最坏的n/2次运行二进制搜索(log )，给出O(n/2 * log )，在大O中是O(n * log n)。
这是正确的吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2017-02-20 13:10:35
是的，这两种算法你的分析都是正确的。
您的第一个算法也使用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和其他拐角处的情况。
Stack Overflow用户
发布于 2017-02-20 13:10:26
这听起来像是你正在选修的某门课程中的作业问题。我不会为您解决这个问题--尽管在网上找到解决方案非常容易--但是我要告诉您，我确信您的解决方案必须花费O(n)时间作为最坏情况的复杂性。基于散列的解决方案每次查找平均只需要O(1)个时间，而的平均时间是0(1)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42345198
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号