为什么使用排序（O(n log n) 复杂度）比使用 HashMap（O(n) 复杂度）更快地找到多数元素？

Question

众数问题：

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.

// Solution1 - Sorting ----------------------------------------------------------------
    class Solution {
        public int majorityElement(int[] nums) {
            Arrays.sort(nums);
            return nums[nums.length/2];
        }
    }

// Solution2 - HashMap ---------------------------------------------------------------
class Solution {
    public int majorityElement(int[] nums) {
        // int[] arr1 = new int[nums.length];
        HashMap<Integer, Integer> map = new HashMap<>(100);  
        Integer k = new Integer(-1);
        try{
            for(int i : nums){
                if(map.containsKey(i)){
                    map.put(i, map.get(i)+1);
                }
                else{
                    map.put(i, 1);
                }
            }
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
                if(entry.getValue()>(nums.length/2)){
                    k = entry.getKey();
                    break;
                }
            }
        }catch(Exception e){
            throw new IllegalArgumentException("Error");
        }
        return k;    
    }
}

Arrays.sort() 函数在 Java 中使用 QuickSort 实现，具有 O(n log n) 时间复杂度。

另一方面，使用HashMap寻找众数的时间复杂度只有O(n)。

因此，解决方案 1（排序） 应该比 解决方案 2 (HashMap) 花费更长的时间，但是当我在LeetCode，解法2的平均耗时比解法1多很多（差不多多了8倍）

为什么会这样？我真的很困惑......

是测试用例大小的原因吗？当测试用例中的元素数量急剧增加时，解决方案 2 会变得更有效吗？

Answer 1

Big O 不是衡量实际表现的标准。它只会让您了解与 n 相比您的性能将如何发展。

实际上，对于某些 n，O(n.logn) 中的算法最终会比 O(n) 慢。但是 n 可能是 1、10、10^6 甚至 10^600 - 此时它可能无关紧要，因为你永远不会运行进入这样的数据集 - 或者你没有足够的硬件来支持它.

软件工程师必须同时考虑实际性能和实际极限性能。例如，哈希映射查找在理论上比未排序的数组查找更快......但是大多数数组都很小（10-100 个元素）由于额外的代码复杂性而否定了任何 O(n) 优势。

你当然可以稍微优化你的代码，但在这种情况下，你不太可能改变小 n 的结果，除非你引入另一个因素（例如，人为地减慢每个周期的时间，并设置一个常数）。

（本来想找个好比喻来说明，没想到比想象中难...）

Answer 2

这取决于测试用例，一些测试用例在 HashMap 中会更快，而另一些则不会。

这是为什么？ 解决方案 1 最坏情况下的受赠人 O(N log₂ N)，但是 HashMap O(N . (M + R)) 其中 M 是冲突成本，R 是调整大小的成本数组。

HashMap内部使用了一个名为table的节点数组，当输入增加或减少时，它会调整不同的时间。您为其分配了初始容量 100。

那么让我们看看会发生什么？ Java 使用单独的链接来解决冲突，一些测试用例可能有很多冲突，导致消耗大量时间查询或更新哈希图。

结论 hashmap的实现受两个因素的影响：1.根据输入的大小调整table数组的大小2.输入中出现了多少碰撞

为什么使用排序（O(n log n) 复杂度）比使用 HashMap（O(n) 复杂度）更快地找到多数元素？

Why is using sorting (O(n log n) complexity) to find the majority element faster than using a HashMap (O(n) complexity)?

java

performance

hashmap

quicksort