Two-Sum - Conception d'algorithme d'optimisation de pré-tri

Question

🧩 Est-il possible d'optimiser le temps d'exécution d'une solution à deux sommes en recevant une entrée pré-triée par ordre croissant ou décroissant?

🚀 Original à deux sommes

Déterminez s'il y a deux articles dont la capacité individuelle sera parfaitement égale à la capacité totale tout en vous assurant que le même article ne peut pas être sélectionné deux fois.

• Entrée: un Int représentant la capacité totale et un tableau d'Int représentant les capacités individuelles des éléments.
• Sortie: valeur booléenne indiquant s'il est possible que deux des éléments correspondent à la capacité totale.
• Complexité temporelle: croissance linéaire, $O(n)$
• Complexité spatiale: croissance linéaire, $O(n)$

Échantillons

Contribution: [4, 5, 2, 6]

• Capacité totale: 10
• Attendre: true

Contribution: [4, 5, 2, 5]

• Capacité totale: 10
• Attendre: true

Contribution: [4, 5, 2, 7]

• Capacité totale: 10
• Attendre: false

Pseudocode

1. Créez un ensemble searchSetpour stocker les éléments qui ont déjà été examinés.

2. Itérer dans le tableau d'entrée des capacités des éléments.

   2a. Recherchez l' targetCapacityélément actuel:totalCapacity - itemCapacity

   2b. Si searchSetcontient le targetCapacity, retournez true.

   2c. Sinon, ajoutez le itemCapacityau searchSet.

3. Renvoie falsesi l'entrée entière est itérée sans trouver de correspondance.

🏗️ Pré-tri

1. Enregistrer une nouvelle var lastTargetCapacity
2. Si le courant itemCapacity< lastTargetCapacity, il n'y a pas de deux sommes possibles et retour false.

c'est à dire

Contribution: [6,2,1,0]

• Capacité totale: 9

Itérations

1. targetCapacity = 9 - 6, lastTargetCapacity= 3
2. Renvoie false car le itemCapacityof 2< lastTargetCapacityof 3.

Answer 1

La solution Two Sum peut être optimisée pour les performances d'exécution étant donné que le tableau d'entrée est pré-trié par ordre croissant ou décroissant.

Si la recherche binaire est utilisée pour trouver ce qui targetCapacityprécède, elle s'exécutera en logarithmique,$O(logn)$, durée d'exécution moyenne. C'est plus rapide que le pseudocode ci-dessus qui s'exécute en linéaire,$O(n)$, runtime utilisant l'itération et le hachage.

Si le tri n'était pas fourni dans l'entrée, il ne serait pas possible de trier et de rechercher plus rapidement que $O(n)$. Le mieux que l'on puisse faire serait$O(nlogn)$ avec une stratégie telle que Quicksort et Binary Search.

Voir: Stanford - Explication de deux sommes

Answer 2

Oui, vous pouvez résoudre le problème à deux sommes en $O(n)$heure, si les nombres sont présentés dans un ordre trié. Voir mon autre réponse pour savoir comment le faire; il s'agit d'un balayage linéaire. Ceci est asymptotiquement optimal, car il faut déjà$O(n)$ le temps même de lire l'entrée, et de résoudre le problème peut nécessiter la lecture de l'ensemble de l'entrée, il ne peut donc plus y avoir d'amélioration asymptotique.