Zwei-Summen-Entwurf eines Optimierungsalgorithmus vor der Sortierung

Nov 23 2020

🧩 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

  1. Erstellen Sie ein Set searchSet, um die bereits untersuchten Elemente zu speichern.

  2. Durchlaufen Sie das Eingabe-Array der Elementkapazitäten.

    2a. Finden Sie die targetCapacityfür den aktuellen Artikel:totalCapacity - itemCapacity

    2b. Wenn das searchSetenthält targetCapacity, kehren Sie zurück true.

    2c. Andernfalls fügen Sie itemCapacitydas hinzu searchSet.

  3. Rückgabe, falsewenn die gesamte Eingabe durchlaufen wird, ohne eine Übereinstimmung zu finden.

🏗️ Vorsortierung

  1. Speichern Sie eine neue Var lastTargetCapacity
  2. Wenn der aktuelle itemCapacity< lastTargetCapacity, gibt es keine möglichen zwei Summen und Rückgabe false.

dh

Eingang: [6,2,1,0]

  • Gesamtkapazität: 9

Iterationen

  1. targetCapacity = 9 - 6, lastTargetCapacity= 3
  2. Geben Sie false zurück, da das itemCapacityvon 2< lastTargetCapacityof 3.

Antworten

AdamHurwitz Nov 28 2020 at 23:41

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 targetCapacityoben 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

D.W. Nov 30 2020 at 12:46

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.