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

Question

多数元素问题：

给定一个大小为 n 的数组，找出多数元素。多数元素是出现多于? n/2 ? 次。你可以假设数组是非空的并且多数元素总是存在于数组中。

// 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() 函数是使用 QuickSort 在 Java 中实现的，时间复杂度为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 的结果，除非您引入另一个因素（例如，用常数人为地减慢每个周期的时间）。

（我想找一个很好的比喻来说明，但是比想象中难……）