1200字范文 > 哈希表的最差复杂度是n2_给定数组A []和数字X 请检查A []中是否有对X | 使用哈希

哈希表的最差复杂度是n2_给定数组A []和数字X 请检查A []中是否有对X | 使用哈希

时间：2018-11-12 18:24:45

哈希表的最差复杂度是n2

Prerequisite:

先决条件：

Hashing data structure

散列数据结构

Problem statement:

问题陈述：

Given an array andasumX, fins any pair which sums toX. Expected time complexityO(n).

给定一个数组和一个和X，对求和为X的任何一对进行求和。预期时间复杂度O(n)。

Example:

例：

Input array:[4, -1, 6, 5, -2, 2]Sum, X=2Output:Pair {4,-2}Explanation:4+(-2)=2 and thus the pair is {4,-2}

Solution:

解：

Obviously, in brute force, we can solve it by checking each pair sums toXor not. In the worst case, it will takeO(n2)which is too costly for the problem. Still, the algorithm would be like the following:

显然，在蛮力中，我们可以通过检查每对和是否等于X来解决。在最坏的情况下，将花费O(n 2 )，这对于该问题而言过于昂贵。尽管如此，该算法仍将如下所示：

For i=0:n-1For j=i+1: n-1If arr[i]+arr[j]==XReturn pair {arr[i],arr[j]}

To solve this efficiently, we will use hashing. What we need to create is a hash table which will be used as our lookup table. The idea is to lookup whetherX-current_elementexists in the hash table or not. If we find any element in the hash table, then obviously

{X-current_element, current_element}is our desired pair.

为了有效解决此问题，我们将使用哈希。我们需要创建一个哈希表，该哈希表将用作我们的查找表。这个想法是要查找哈希表中是否存在X-current_element。如果我们在哈希表中找到任何元素，那么显然

{X-current_element，current_element}是我们想要的对。

Now, we can create a lookup table by simply inserting each element. Then in another loop, we can start finding whetherX-current_elementis in the hash table or not. Following is the two-pass algorithm,

现在，我们只需插入每个元素即可创建查找表。然后在另一个循环中，我们可以开始查找X-current_element是否在哈希表中。以下是两次通过算法，

Create a hash table using set

使用set创建哈希表

unordered_set<int> myset;//first pass->building the hash tableFor i=0 to n-1current_element=arr[i]Add current_element to look up table, myset if it’s not there End for

Find the pair

找到一对

//second pass-> finding the pair using the hash table builtFor i=0 to n-1current_element=arr[i]if(X-current_element is in myset)the desired pair is { current_element , X-current_element } and return End for

The time complexity of the algorithm is of course O(n) and space complexity is also O(n) for the hash table.

该算法的时间复杂度当然是O(n)，而哈希表的空间复杂度也是O(n)。

Now, we can further optimize the above algorithm into a single pass.

现在，我们可以将上述算法进一步优化为一次通过。

Instead of creating the hash table in a separate pass, we can do both searching and creating in one pass. The idea is ifX-current_elementis in the hash table then we are done, otherwise, add thiscurrent_elementto the hash table.

除了在单独的过程中创建哈希表，我们还可以一次完成搜索和创建过程。这个想法是，如果X-current_element在哈希表中，那么我们完成了，否则，请将此current_element添加到哈希表中。

So the algorithm would be:

因此，算法为：

//both searching and looking at a timeFor i=0 to n-1current_element=arr[i]if(X-current_element is in myset)the desired pair is { current_element , X-current_element } and return ElseAdd current_element to mysetEnd for

So, how it guarantees to work?

那么，它如何保证工作呢？

We can show that by our example. Where input array is [4, -1, 6, 5, -2, 2]

If we have used the two-pass algorithm then, we have got {4,-2} as a pair where 4 would be thecurrent_elementand-2 would be theX-current_element.

我们可以通过示例来证明这一点。输入数组为[4，-1，6，5，-2，2]

如果我们使用了两次遍历算法，那么我们将{4，-2}作为一对，其中4是current_element，-2是X-current_element。

But if we use the one-pass algorithm we would get the pair as {-2, 4} where -2 would be thecurrent_elementand 4 would beX-current_element.

但是，如果使用单次通过算法，则该对将为{-2，4}，其中-2为current_element，而4为X-current_element。

The reason is when we have 4 as ourcurrent_elementin our one-pass algorithm then the hash table is empty. Thus we simply add 4.

原因是当我们在一次通过算法中将4作为current_element时，哈希表为空。因此，我们只需添加4。

But when we process -2 as ourcurrent_elementwe have X-(-2) to look for which is 2-(-2) and 4 now exists. So the thing is the one pass is guaranteed to work. Only it will return the pair in reverse order.

但是，当我们将-2作为current_element处理时，我们有X-(-2)来寻找哪个是2-(-2)且现在存在4。因此，事情是一站式保证有效。只有它会以相反的顺序返回该对。

The time & space complexity of the one-pass algorithm is of course same as the two-pass algorithm since it's bigOnotation.

一遍算法的时间和空间复杂度当然与二遍算法相同，因为它的O表示法很大。

C++ implementation:

C ++实现：

#include <bits/stdc++.h>using namespace std;pair<int, int> find_pair_sum(vector<int> arr, int n, int X){unordered_set<int> myset;for (int i = 0; i < n; i++) {//pair exists current_element, X-current_elementif (myset.find(X - arr[i]) != myset.end()) {return make_pair(arr[i], X - arr[i]);}//if arr[i] already not thereelse if (myset.find(arr[i]) == myset.end()) myset.insert(arr[i]);}return make_pair(INT_MAX, INT_MAX);}int main(){cout << "Enter number of input elements,n\n";int n;cin >> n;cout << "Enter the input elements\n";vector<int> arr(n);for (int i = 0; i < n; i++)cin >> arr[i];cout << "Enter sum, X\n";int X;cin >> X;pair<int, int> p = find_pair_sum(arr, n, X);if (p.first == INT_MAX && p.second == INT_MAX)cout << "No pairs found\n";elsecout << "The pairs are : " << p.first << ", " << p.second << endl;return 0;}

Output:

输出：

Enter number of input elements,n6Enter the input elements4 -1 6 5 2 -2Enter sum, X2The pairs are : -2, 4