Como desenvolver um

Dada uma matriz classificada de números inteiros, quero encontrar o número de pares que somam $0$ . Por exemplo, dado $\{-3,-2,0,2,3,4\}$ , o número de pares soma a zero é $2$ .

Deixei $N$ seja o número de elementos na matriz de entrada. Se eu usar a pesquisa binária para encontrar o aditivo inverso para um elemento na matriz, a ordem será $O(\log N)$ . Se eu percorrer todos os elementos do conjunto, a ordem será $O(N\log N)$ .

Como encontrar um algoritmo de ordem $O(N)$ ?

algorithms Laura
fonte

k

$k$ O problema -SUM geralmente se refere a um problema ligeiramente diferente, onde se tenta encontrar um conjunto de

k

$k$ elementos da matriz de entrada

A

$A$ de modo que eles somam zero. Em um determinado modelo de computação, é impossível obter um algoritmo de tempo linear para

k = 2

$k=2$ ou para qualquer

k

$k$ . Veja esta pergunta .

Juho

Respostas:

Deixei $A$ seja a matriz de entrada classificada. Mantenha dois ponteiros $l$ e $r$ que passam pelos elementos em $A$ . O ponteiro $l$ passará pela "parte esquerda" de $A$ , ou seja, números inteiros negativos. O ponteiro $r$ faz o mesmo para a "parte direita", os números inteiros positivos. Abaixo, descreverei uma solução de pseudocódigo e assumirei que $0 \notin A$ para menor simplicidade. Omitidas também são as verificações dos casos em que existem apenas números inteiros positivos ou negativos em $A$ .

COUNT-PAIRS(A[1..N]):
 l = index of the last negative integer in A
 r = index of the first positive integer in A
 count = 0;

 while(l >= 0 and r <= N)
   if(A[l] + A[r] == 0)
     ++count; ++right; --left; continue;

   if(A[r] > -1 * A[l]) 
     --left;
   else 
     ++right;

É óbvio que o algoritmo leva $O(N)$ Tempo.

Juho
fonte

Você provavelmente deve adicionar um argumento para correção.

Raphael

-1

A abordagem mais simples, pelo que entendi, parece usar uma tabela de hash, H = {a [0] = true, .., a [n-1] = true}. Esta tabela de hash pode ser construída em O (n) tempo. Depois que a Hash-Table for criada, itere através de A [0, .., n-1] e verifique se H [-1 * a [i]] existe. Caso isso aconteça, aumente um contador em 1 e retorne o resultado final. Isto é claramente O (n).

Juspreet Sandhu
fonte

As expressões H = {a [0] = true, .., a [n-1] = true} e A [0, .., n-1] não fazem sentido para mim. Ao usar uma função hash, a matriz nem precisa ser classificada. Mas algoritmos que usam a função hash usam algumas propriedades pseudo-aleatórias da função hash. Na pior das hipóteses, todos os itens serão mapeados para o mesmo valor de hash e o algoritmo é quadrático. Não sei quais são os requisitos do OP.

miracle173

Veja minha implementação disso abaixo e me diga como é quadrática no pior dos casos.

Sammy

@ miracle173: Isso é apenas conveniência para notação. Posso representar a tabela de hash como um conjunto de pares de valor-chave (que é o que realmente é, matematicamente falando). O arranjo real na memória é desnecessário para detalhes teóricos sobre complexidade. E, as funções Hash são projetadas para evitar colisões, desde que haja entropia de sementes suficiente. Eu respondi com o porque a resposta de Juho assume um "A classificado", que implica implicitamente a complexidade O (n log (n)) e * NOT O (n).

Juspreet Sandhu

@ manbearpig1 O User Evil já adicionou um comentário em sua postagem que deve responder à sua pergunta. O pior caso da pesquisa de tabela de hash é O (n) e, portanto, o pior caso de todo o algoritmo é O (n ^ 2).

precisa saber é o seguinte

O @JuspreetSandhu Usere Evil adicionou um comentário a outra resposta que explicava o problema das funções de hash.

precisa saber é o seguinte

-1

Observe que podemos procurar um valor em um Python definido em tempo constante.

def twoSum(data):
    count = 0
    nums = set()
    for num in data:
        if (num * -1) in nums:
            count += 1
        nums.add(num)
    return count

sammy
fonte

Não é tempo constante, mas tempo constante esperado. Pode haver uma tabela de hash, uma árvore (auto) balanceada ou uma estrutura semelhante. Isso dá o esperado

O (1)

$\mathcal O(1)$ mas pode ser

O (n)

$\mathcal O(n)$ em caso degradado para tabela de hash ou

O (\log n)

$\mathcal O(\log n)$ para árvore. Além disso, preferimos o pseudocódigo, porque nem todo mundo entende python, portanto, não é óbvio o porquê ou como ele funciona. Na pior das hipóteses, para a tabela de hash em que todos os valores são mapeados em uma posição, o tempo para obter o elemento é

O (n)

$\mathcal O(n)$ . Você executa esta etapa

n

$n$ vezes por isso dá

O (n^{2})

$\mathcal O(n^2)$ no pior dos casos.

Mal