我试图阐明如何为以下情况计算 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),因为您需要在最坏情况下运行二分查找 (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/