Gegeben drei Listen: A, B und C der Länge n jeder. Wenn drei 3 Zahlen (1 aus jeder Liste), summieren sich bis Null zurück wahr. Ich möchte dies mit o (n) Komplexität zu lösen. Ich habe die Listen sortiert und ich kann eine Hash-Karte mit der Summe von 2 erstellen verknüpfte Listen oder 3 Listen miteinander vergleichen [o (n * n * n)] .Schlage einige Wege vor, die Methoden zu improvisieren, um die Komplexität zu reduzieren..Ich kann mir keine vorstellen ... Danke in adv
Ich denke nicht, dass es in o(n²) (dh wirklich besser als n² ) möglich ist, aber es kann in O(n²) (dh wie n² ) als getan werden folgt:
Als erstes reverse list B , um B' zu erhalten (dauert O(n) time), eine Liste, deren Einträge in absteigender Reihenfolge sortiert sind. Zuerst betrachten wir das Problem, zwei Elemente in den Listen A und B' zu finden, die zu einer gegebenen Zahl summieren:
Wir können das folgendermaßen machen (Python-Code):
%Vor% Laufzeit des oben genannten ist O(n) . Zusätzlicher Platzbedarf ist O(1) , da wir nur zwei Zeiger speichern müssen. Beachten Sie, dass das Obige leicht transformiert werden kann, so dass es mit doppelt verknüpften Listen funktioniert.
Dann müssen wir insgesamt nur Folgendes tun:
%Vor% Daraus ergibt sich die Laufzeit O(n²) und zusätzlicher Speicherplatz O(1) .
Die Listen sind sortiert, oder? Erstellen Sie ein sortiertes Array C ' aus C in O ( n ) Zeit.
Für jedes der n ² Paare x , y in A × B , überprüfe ob - ( x + y ) in C ' mit binärer Suche ist. Die gesamte Zeitkomplexität ist O ( n ² lg n ), die Raumkomplexität ist O ( n ).
Durch das Erstellen einer Hash-Tabelle aus C wird die Zeitkomplexität weiter auf O ( n ²) reduziert, und zwar auf Kosten von O (1) Hash-Tabellen.
Sie können dies nicht mit O (n) -Komplexität machen, da es ein NP-vollständiges Problem ist (außer P = NP). Sehen Sie sich die Wiki-Seite zum Subset-Sum-Problem für mögliche Lösungen an.
Tags und Links algorithm time-complexity linked-list