Улучшение сложности времени - PullRequest
Новая
       8

Улучшение сложности времени

0 голосов
/ 12 ноября 2018

Буду признателен за отзыв о цикле Big-O (сложность по времени) или способах его улучшения.

Давайте рассмотрим следующее: 

var pairs = 0;
HashSet<int> hs = new HashSet<int>(n);
for (var i = 0; i < ar.Length; i++)
{
    if(!hs.Contains(ar[i]))
        hs.Add(ar[i]);
    else
    {
        pairs++;
        hs.Remove(ar[i]);
    }
}

return pairs;

Изчто я могу определить, наихудшая временная сложность описанного выше: O (n) из-за цикла.

Есть ли способ улучшить это, чтобы приблизить сложность времени кO (1) насколько это возможно?

PS: Я уверен, что вышеизложенное никогда не будет O (1).

Спасибо

...