java - 为什么使用排序(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() 函数是使用 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 的结果。

(我想找一个好的比喻来说明，但比预期的要难……)