Comment développer un

Étant donné un tableau trié d'entiers, je veux trouver le nombre de paires qui totalisent . Par exemple, étant donné , le nombre de paires somme à zéro est . $0$ $\{-3,-2,0,2,3,4\}$ $2$

Soit le nombre d'éléments dans le tableau d'entrée. Si j'utilise la recherche binaire pour trouver l'inverse additif d'un élément du tableau, l'ordre est . Si je traverse tous les éléments de l'ensemble, alors l'ordre est . $N$ $O(\log N)$ $O(N\log N)$

Comment trouver un algorithme d'ordre ? $O(N)$

algorithms Laura
la source

k

$k$ -Le problème SUM fait généralement référence à un problème légèrement différent, où l'on essaie de trouver un ensemble de

k

$k$ éléments du tableau d'entrée

A

$A$ de sorte qu'ils totalisent zéro. Dans un certain modèle de calcul, il est impossible d'obtenir un algorithme de temps linéaire pour

k = 2

$k=2$ , ou pour tout même

k

$k$ . Voir cette question .

Juho

Réponses:

Laisser $A$ être le tableau d'entrée trié. Gardez deux pointeurs $l$ et $r$ qui passent par les éléments $A$ . Le pointeur $l$ passera par la "partie gauche" de $A$ , ce sont les entiers négatifs. Le pointeur $r$ fait de même pour la "partie droite", les entiers positifs. Ci-dessous, je vais décrire une solution de pseudocode et supposer que $0 \notin A$ pour une simplicité mineure. Omettent également les vérifications pour les cas où il n'y a que des nombres entiers positifs ou négatifs dans $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;

Il est évident que l'algorithme prend $O(N)$ temps.

Juho
la source

Vous devriez probablement ajouter un argument pour l'exactitude.

Raphael

-1

Selon moi, l'approche la plus simple semble être d'utiliser une table de hachage, H = {a [0] = true, .., a [n-1] = true}. Cette table de hachage peut être construite en temps O (n). Une fois la table de hachage construite, parcourez A [0, .., n-1] et vérifiez si H [-1 * a [i]] existe. Si c'est le cas, incrémentez un compteur de 1 et retournez le résultat final. C'est clairement O (n).

Juspreet Sandhu
la source

Les expressions H = {a [0] = true, .., a [n-1] = true} et A [0, .., n-1] n'ont aucun sens pour moi. Lorsque vous utilisez une fonction de hachage, le tableau ne doit même pas être trié. Mais les algorithmes utilisant la fonction de hachage utilisent certaines propriétés pseudo-aléatoires de la fonction de hachage. Dans le pire des cas, tous les éléments seront mappés à la même valeur de hachage et l'algorithme est quadratique. Je ne sais pas quelles sont les exigences du PO.

miracle173

Voir ma mise en œuvre de cela ci-dessous et dites-moi comment c'est quadratique dans le pire des cas.

sammy

@ miracle173: C'est juste une commodité pour la notation. Je peux représenter la table de hachage comme un ensemble de paires clé-valeur (ce qui est en fait mathématiquement). L'arrangement réel en mémoire n'est pas nécessaire pour les détails théoriques concernant la complexité. De plus, les fonctions de hachage sont conçues pour éviter les collisions à condition que l'entropie des graines soit suffisante. J'ai répondu par parce que la réponse de Juho suppose un "A trié", ce qui rend implicitement la complexité O (n log (n)) et * NOT O (n).

Juspreet Sandhu

@ manbearpig1 User Evil a déjà ajouté un commentaire à votre message qui devrait répondre à votre question. Le pire cas de la recherche de table de hachage est O (n) et donc le pire de tout l'algorithme est O (n ^ 2).

miracle173

@JuspreetSandhu Usere Evil a ajouté un commentaire à une autre réponse qui expliquait le problème avec les fonctions de hachage.

miracle173

-1

Notez que nous pouvons rechercher une valeur dans un ensemble Python en temps constant.

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

sammy
la source

Ce n'est pas un temps constant mais un temps constant attendu. Il peut y avoir une table de hachage, un arbre (auto) équilibré ou une structure similaire. Cela donne

O (1)

$\mathcal O(1)$ mais ça peut être

O (n)

$\mathcal O(n)$ en cas dégradé pour table de hachage ou

O (\log n)

$\mathcal O(\log n)$ pour l'arbre. En outre, ici, nous préférons le pseudocode car tout le monde ne comprend pas le python, il n'est donc pas évident de savoir pourquoi ni comment cela fonctionne. Dans le pire des cas pour la table de hachage où chaque valeur est mappée dans un seul bac, le temps d'obtention de l'élément est

O (n)

$\mathcal O(n)$ . Vous effectuez cette étape

n

$n$ fois donc ça donne

O (n^{2})

$\mathcal O(n^2)$ au pire des cas.

Evil