Почему эти l oop & операции хеширования занимают O (N) временную сложность? - PullRequest
Новая
       122

Почему эти l oop & операции хеширования занимают O (N) временную сложность?

0 голосов
/ 30 мая 2020

Для массива: 

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

Вам предлагается найти число в массиве, которое встречается нечетное количество раз. Это 3 (встречается 3 раза). Временная сложность должна быть не менее O (n). Решение - использовать HashMap. Элементы становятся ключами , а их счетчиками становятся значениями хэш-карты. 

// 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) временная сложность. Если подумать, только l oop требует O (N) временной сложности. Эти hmap.put (операция вставки) и hmap.get (операции поиска) принимают O (N) , и они вложены в l oop. Обычно я думаю, что эта функция занимает O (N ^ 2) раз. Почему вместо этого требуется O (N) ?.

Ответы [ 2 ]

1 голос
/ 30 мая 2020

Я не понимаю, почему эта общая операция занимает O (N) временной сложности.

Вы должны проверить все элементы массива - O(N)

Для каждого элемента массива, который вы вызываете contain, get и put в массиве. Это O(1) операций. Или, точнее, они составляют O(1) при среднем , амортизированных за время жизни HashMap. Это связано с тем, что HashMap будет увеличивать свой массив ha sh, когда отношение размера массива к количеству элементов превышает коэффициент загрузки.

O (N) повторений 2 или 3 O (1) операций - это O (N). QED

Ссылка:

Строго говоря есть несколько сценариев ios, где HashMap не O(1).

  • Если функция ha sh плохая (или распределение ключей патологическое), ha sh цепи будут разбалансированы. В ранних реализациях HashMap это могло привести (в худшем случае) к операциям O(N), потому что такие операции, как get, должны были искать длинную цепочку ha sh. В последних реализациях HashMap построит сбалансированное двоичное дерево для любой слишком длинной цепочки ha sh. Это приводит к наихудшему случаю O(logN) операций.

  • HashMap не может вырастить массив ha sh за пределы 2 ^ 31 га sh ведер. Итак, в этот момент HashMap сложность начинает переходить в O(log N) сложность. Однако, если у вас есть карта такого размера, другие вторичные эффекты, вероятно, все равно повлияют на реальную производительность.

1 голос
/ 30 мая 2020

Алгоритм сначала выполняет итерацию по массиву чисел размером n, чтобы сгенерировать карту с количеством вхождений. Должно быть понятно, почему это операция O(n). Затем, после того, как хэш-карта была построена, она выполняет итерацию по этой карте и находит все записи, счетчики которых являются нечетными числами. Размер этой карты на практике будет где-то между 1 (в случае, если все входные числа одинаковы) и n (в случае, когда все входные данные разные). Таким образом, эта вторая операция также ограничена O(n), оставляя весь алгоритм O(n).

...