与 "Find a pair with the given difference" 中的时间复杂度混淆
Confusion with time complexity in "Find a pair with the given difference"
我正在尝试通过算法学习时间复杂度。我发现这个问题很有趣，上面写着："Find the pairs with the given difference"。我了解问题并缩小到 2 种方法，它们是：
1. Using Binary search (Time complexity: O(nLogn) in worst case)
2. Use hash (Time comlexity: O(n), Space complexity : O(n))
谁能解释一下哪一个更适合实施。谢谢。
在引用的情况下我指的是这个问题：
http://www.geeksforgeeks.org/count-pairs-difference-equal-k/
Please can someone explain which one is better to implement.
这是设计方案，没有明确的答案。每种解决方案都有其优点和缺点，选择 "correct" 取决于实际需求。
一些示例注意事项：
- 如果你的内存非常有限，或者元素流非常大（假设它在大小为 10GB 的文件上），哈希解决方案变得不可行，因为你不能将它存储在内存中，并且排序解决方案 +二分查找变得更有吸引力。
- 如果您希望大型数组的平均时间尽可能快，并且您拥有尽可能多的内存 - 由于
O(n) 平均时间复杂度，散列解决方案变得更具吸引力。
- 如果您的应用程序是实时运行的，并且您负担不起，无论如何都将花费
O(n^2) 时间，无论这种可能性有多低 - 它都会破坏您的公司。由于哈希解决方案在最坏的情况下（非常罕见的情况）会衰减到 O(n^2)，因此您会想要避免它，并且再次 - 排序变得更有吸引力。
- 由于两者都比较高效，并且如果没有真正的限制（这可能是 99% 的情况），那么更容易实现和维护的是您应该选择的。
我正在尝试通过算法学习时间复杂度。我发现这个问题很有趣，上面写着："Find the pairs with the given difference"。我了解问题并缩小到 2 种方法，它们是：
1. Using Binary search (Time complexity: O(nLogn) in worst case)
2. Use hash (Time comlexity: O(n), Space complexity : O(n))
谁能解释一下哪一个更适合实施。谢谢。
在引用的情况下我指的是这个问题： http://www.geeksforgeeks.org/count-pairs-difference-equal-k/
Please can someone explain which one is better to implement.
这是设计方案，没有明确的答案。每种解决方案都有其优点和缺点，选择 "correct" 取决于实际需求。
一些示例注意事项：
- 如果你的内存非常有限，或者元素流非常大（假设它在大小为 10GB 的文件上），哈希解决方案变得不可行，因为你不能将它存储在内存中，并且排序解决方案 +二分查找变得更有吸引力。
- 如果您希望大型数组的平均时间尽可能快，并且您拥有尽可能多的内存 - 由于
O(n)平均时间复杂度，散列解决方案变得更具吸引力。 - 如果您的应用程序是实时运行的，并且您负担不起，无论如何都将花费
O(n^2)时间，无论这种可能性有多低 - 它都会破坏您的公司。由于哈希解决方案在最坏的情况下（非常罕见的情况）会衰减到O(n^2)，因此您会想要避免它，并且再次 - 排序变得更有吸引力。 - 由于两者都比较高效，并且如果没有真正的限制（这可能是 99% 的情况），那么更容易实现和维护的是您应该选择的。