Zwei-Summen-Entwurf eines Optimierungsalgorithmus vor der Sortierung
🧩 Ist es möglich, die Laufzeit einer Zwei-Summen-Lösung zu optimieren, indem eine vorsortierte Eingabe in aufsteigender oder absteigender Reihenfolge empfangen wird?
🚀 Ursprüngliche Zwei-Summe
Bestimmen Sie, ob es zwei Elemente gibt, deren individuelle Kapazität perfekt der Gesamtkapazität entspricht, und stellen Sie gleichzeitig sicher, dass dasselbe Element nicht zweimal ausgewählt werden kann.
- Eingabe: Ein Int, das die Gesamtkapazität darstellt, und ein Array von Ints, die die individuellen Kapazitäten der Elemente darstellen.
- Ausgabe: Ein Boolescher Wert, der angibt, ob zwei der Elemente der Gesamtkapazität entsprechen können.
- Zeitliche Komplexität: Lineares Wachstum, $O(n)$
- Raumkomplexität: Lineares Wachstum, $O(n)$
Proben
Eingang: [4, 5, 2, 6]
- Gesamtkapazität:
10
- Erwarten von:
true
Eingang: [4, 5, 2, 5]
- Gesamtkapazität:
10
- Erwarten von:
true
Eingang: [4, 5, 2, 7]
- Gesamtkapazität:
10
- Erwarten von:
false
Pseudocode
Erstellen Sie ein Set
searchSet
, um die bereits untersuchten Elemente zu speichern.Durchlaufen Sie das Eingabe-Array der Elementkapazitäten.
2a. Finden Sie die
targetCapacity
für den aktuellen Artikel:totalCapacity - itemCapacity
2b. Wenn das
searchSet
enthälttargetCapacity
, kehren Sie zurücktrue
.2c. Andernfalls fügen Sie
itemCapacity
das hinzusearchSet
.Rückgabe,
false
wenn die gesamte Eingabe durchlaufen wird, ohne eine Übereinstimmung zu finden.
🏗️ Vorsortierung
- Speichern Sie eine neue Var
lastTargetCapacity
- Wenn der aktuelle
itemCapacity
<lastTargetCapacity
, gibt es keine möglichen zwei Summen und Rückgabefalse
.
dh
Eingang: [6,2,1,0]
- Gesamtkapazität:
9
Iterationen
targetCapacity = 9 - 6
,lastTargetCapacity
= 3- Geben Sie false zurück, da das
itemCapacity
von2
<lastTargetCapacity
of3
.
Antworten
Die Zwei-Summen-Lösung kann für die Laufzeitleistung optimiert werden, da das Eingabearray in aufsteigender oder absteigender Reihenfolge vorsortiert ist.
Wenn die binäre Suche verwendet wird, um das targetCapacity
oben Gesagte zu finden , wird sie logarithmisch ausgeführt.$O(logn)$, durchschnittliche Laufzeit. Dies ist schneller als der Pseudocode darüber, der linear läuft.$O(n)$, Laufzeit mit Iteration und Hashing.
Wenn in der Eingabe keine Sortierung vorgesehen wäre, wäre es nicht möglich, schneller als zu sortieren und zu suchen $O(n)$. Das Beste, was getan werden könnte, wäre$O(nlogn)$ mit einer Strategie wie Quicksort und Binary Search.
Siehe: Stanford - Zwei-Summen-Erklärung
Ja, Sie können das Zwei-Summen-Problem in lösen $O(n)$Zeit, wenn die Zahlen in sortierter Reihenfolge angezeigt werden. Siehe meine andere Antwort, wie es geht; es handelt sich um einen linearen Scan. Dies ist asymptotisch optimal, wie es bereits dauert$O(n)$ Die Zeit zum Lesen der Eingabe und zum Lösen des Problems erfordert möglicherweise das Lesen der gesamten Eingabe, sodass keine weitere asymptotische Verbesserung möglich ist.