Почему отправка кода leet с O (n) сложностью времени занимает больше времени, чем O (n log n) сложность времени?

Question

Я решил следующий вопрос о Leetcode -

Given two arrays, write a function to compute their intersection.

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Я разработал решение с O (n) T. C в java, используя HashMap, как показано ниже:

Подход-1

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
       int res[] = new int[nums1.length];
       Map<Integer,Integer> freqMap = new HashMap<Integer,Integer>();
        for(int i=0;i<nums1.length;i++){
          freqMap.put(nums1[i],freqMap.getOrDefault(nums1[i],0)+1);
        }
    int k = 0;
    for(int i=0;i<nums2.length;i++){
        if(freqMap.get(nums2[i]) != null && freqMap.get(nums2[i]) != 0){
           res[k] = nums2[i]; 
           freqMap.put(nums2[i],freqMap.get(nums2[i])-1);
           k++;
        }
      }
     return Arrays.copyOfRange(res,0,k);
    }
}

Я видел другое принятое решение с O (nlogn) T. C с использованием подхода сортировки, как показано ниже:

Подход-2

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0, j = 0, k = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            ++i;
        } else if (nums1[i] > nums2[j]) {
            ++j;
        } else {
            nums1[k++] = nums1[i++];
            ++j;
        }
    }
    return Arrays.copyOfRange(nums1, 0, k);
}
}

Теперь, теоретически решение Подход-1 должно работать быстрее, чем Подход-2, но решение Подход-2 работало за 1 мс, тогда как решение Подход-1 работало за 2 мс.

Кто-нибудь может объяснить, почему это может произойти?

PS - Время выполнения было рассчитано по коду leetcode при отправке

Edit- С новыми комментариями я размышляю над некоторыми новыми вопросами сейчас.

Так как, похоже, на это влияет постоянный фактор в большом О. Я хотел бы знать, какие факторы могут вызвать разницу во времени в этом конкретном случае c?

И всегда ли лучше использовать сортировку по массиву по Hashmap для вычислений с целочисленным значением n?

Answer 1

Существуют бесконечные переменные, которые могут влиять на время выполнения, дисперсию, соединение, нагрузку просекора, способ размещения вещей в памяти и т. Д. По этой причине мы используем нотацию O (n), так как это единственный разумный способ сравнить два алгоритма.

Также некоторые алгоритмы имеют большую фиксированную стоимость, что означает, что они медленнее, когда n мало, потому что масштабирование фактор не получает достаточно данных для масштабирования.

Когда мы вычисляем O (n), мы исключаем постоянные затраты, так как когда n становится большим, постоянные затраты означают все меньше и меньше с точки зрения используемого времени. Таким образом, наша большая нотация O не будет различать 999n и n, хотя последняя выполняет меньше операций. Помните, что 10n медленнее (больше операций), чем n ^ 2, когда n <10, даже если O (n) считается быстрее, чем O (n ^ 2) </p>