为什么这些循环和哈希操作需要 O(N) 时间复杂度？

Question

给定数组：

int arr[]= {1, 2, 3, 2, 3, 1, 3}

您需要在数组中找到一个出现奇数次的数字。它是 3（出现 3 次）。时间复杂度至少应该是 O(n)。解决方案是使用 HashMap。元素成为 keys 并且它们的 counts 成为 hashmap 的值。

// Code belongs to geeksforgeeks.org
// function to find the element occurring odd 
    // number of times 

    static int getOddOccurrence(int arr[], int n) 
    { 
        HashMap<Integer,Integer> hmap = new HashMap<>(); 
        // Putting all elements into the HashMap 
        for(int i = 0; i < n; i++) 
        { 
            if(hmap.containsKey(arr[i])) 
            { 
                int val = hmap.get(arr[i]); 
                // If array element is already present then 
                // increase the count of that element. 
                hmap.put(arr[i], val + 1);  
            } 
            else
                // if array element is not present then put 
                // element into the HashMap and initialize  
                // the count to one. 
                hmap.put(arr[i], 1);  
        } 

        // Checking for odd occurrence of each element present 
          // in the HashMap  
        for(Integer a:hmap.keySet()) 
        { 
            if(hmap.get(a) % 2 != 0) 
                return a; 
        } 
        return -1; 
    }

我不明白为什么整个操作需要 O(N) 时间复杂度。如果我考虑一下，仅循环就需要 O(N) 时间复杂度。那些 hmap.put（插入操作）和 hmap.get（查找操作）采用 O(N) 并且它们嵌套在循环中。所以通常我会认为这个函数需要 O(N^2) 次。为什么它需要 O(N)?.

Answer 1

该算法首先迭代大小为 n 的数字数组，以生成包含出现次数的地图。应该很清楚为什么这是一个O(n)操作。然后，在构建 hashmap 之后，它会迭代该映射并找到所有计数为奇数的条目。该映射的大小实际上介于 1（在所有输入数字相同的情况下）和 n（在所有输入不同的情况下）之间。所以，这第二个操作也受 O(n) 的限制，留下整个算法 O(n).

Answer 2

I don't get why this overall operation takes O(N) time complexity.

您必须检查数组的所有元素 - O(N)

对于数组的每个元素，您在数组上调用 contain、get 和 put。这些是 O(1) 操作。或者更准确地说，它们 O(1) 平均 在 HashMap 的生命周期内摊销。这是因为当数组大小与元素数量的比率超过负载因子时，HashMap 将增长其哈希数组。

O(N) 2 或 3 O(1) 操作的重复是 O(N)。 QED

参考：

Is a Java hashmap really O(1)?

严格来说，有几种情况 HashMap 不是 O(1)。

如果哈希函数不好（或者密钥分布不正常），哈希链就会不平衡。对于早期的 HashMap 实现，这可能会导致（最坏的情况）O(N) 操作，因为像 get 这样的操作必须搜索长哈希链。在最近的实现中，HashMap 将为任何太长的哈希链构造平衡二叉树。这会导致最坏情况 O(logN) 操作。
HashMap 无法将哈希数组增长到超过 2^31 个哈希桶。所以在那个时候 HashMap 复杂性开始过渡到 O(log N) 复杂性。然而，如果你有一张那么大的地图，其他次要效果可能会影响实际性能。

为什么这些循环和哈希操作需要 O(N) 时间复杂度？

Why are these loop & hashing operations take O(N) time complexity?

java

big-o

loops

hashmap