为什么这些循环和散列运算需要O（N）时间复杂度？

Question

给出数组：

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

被要求在数组中查找发生次数[[odd次的数字。是3（发生3次）。时间复杂度至少应为O（n）。解决方法是使用HashMap。元素变为keys，它们的counts成为哈希图的值。

// 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

我不明白为什么整个操作需要O（N）的时间复杂度。

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

对于数组的每个元素，您在数组上调用contain，get和put。这些是O(1)操作。更准确地说，它们平均为O(1)

在[C0的寿命期间摊销]。这是由于以下事实：当数组大小与元素数之比超过负载因子时，HashMap将增长其哈希数组。

O（N）个2或3个O（1）运算的重复是O（N）。 QED

参考：

HashMap

---

严格来说，有几种情况，Is a Java hashmap really O(1)?不是HashMap。

• 如果哈希函数差（或密钥分配是病态的），则哈希链将不平衡。在早期的O(1)实现中，这可能会导致（最坏的情况）HashMap操作，因为类似O(N)的操作必须搜索较长的哈希链。在最近的实现中，get将为任何太长的哈希链构造一个平衡的二叉树。这会导致最坏的情况HashMap操作。
• O(logN)无法将哈希数组扩展到2 ^ 31个哈希桶以上。因此，此时HashMap复杂度开始转变为HashMap复杂度。但是，如果您有一个如此大小的地图，无论如何，其他次要效果也可能会影响实际性能。

Answer 2

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