Two-Sum - Pre-sort Optimization Algorithm Design

Question

🧩 È possibile ottimizzare il tempo di esecuzione di una soluzione a due somme ricevendo un input preordinato in ordine crescente o decrescente?

🚀 Due somme originali

Determina se ci sono due elementi la cui capacità individuale sarà perfettamente uguale alla capacità totale assicurandoti che lo stesso elemento non possa essere selezionato due volte.

• Input: un Int che rappresenta la capacità totale e un array di Int che rappresenta le capacità individuali degli elementi.
• Output: un valore booleano che rappresenta se è possibile che due elementi siano uguali alla capacità totale.
• Complessità temporale: crescita lineare, $O(n)$
• Complessità spaziale: crescita lineare, $O(n)$

Campioni

Ingresso: [4, 5, 2, 6]

• Capacità totale: 10
• Aspettarsi: true

Ingresso: [4, 5, 2, 5]

• Capacità totale: 10
• Aspettarsi: true

Ingresso: [4, 5, 2, 7]

• Capacità totale: 10
• Aspettarsi: false

Pseudocodice

1. Crea un set searchSetper memorizzare gli elementi che sono già stati esaminati.

2. Scorri la matrice di input delle capacità degli elementi.

   2a. Trova l' targetCapacityelemento corrente:totalCapacity - itemCapacity

   2b. Se searchSetcontiene targetCapacity, restituisci true.

   2c. Altrimenti, aggiungi itemCapacityil file searchSet.

3. Restituisce falsese l'intero input viene iterato senza trovare una corrispondenza.

🏗️ Pre-ordinamento

1. Salva una nuova var lastTargetCapacity
2. Se l'attuale itemCapacity< lastTargetCapacity, non ci sono due somme possibili e ritorno false.

cioè

Ingresso: [6,2,1,0]

• Capacità totale: 9

Iterazioni

1. targetCapacity = 9 - 6, lastTargetCapacity= 3
2. Restituisce false perché itemCapacitydi 2< lastTargetCapacitydi 3.

Answer 1

La soluzione Two Sum può essere ottimizzata per le prestazioni di runtime dato che la matrice di input è preordinata in ordine crescente o decrescente.

Se la ricerca binaria viene utilizzata per trovare quanto targetCapacitysopra, verrà eseguita in modo logaritmico,$O(logn)$, tempo di esecuzione medio. Questo è più veloce dello pseudocodice sopra che funziona in lineare,$O(n)$, runtime utilizzando iterazione e hashing.

Se l'ordinamento non fosse fornito nell'input, non sarebbe possibile ordinare e cercare più velocemente di $O(n)$. Il meglio che si potrebbe fare sarebbe$O(nlogn)$ con una strategia come Quicksort e Binary Search.

Vedi: Stanford - Two Sum Explanation

Answer 2

Sì, puoi risolvere il problema delle due somme in $O(n)$tempo, se i numeri sono presentati in ordine ordinato. Vedi la mia altra risposta per come farlo; implica una scansione lineare. Questo è asintoticamente ottimale, poiché già ci vuole$O(n)$ tempo anche per leggere l'input e risolvere il problema può richiedere la lettura dell'intero input, quindi non ci possono essere ulteriori miglioramenti asintotici.