Heute bat uns der Lehrer in der Schule, einen Duplikat-Lösch-Algorithmus zu implementieren. Es ist nicht so schwierig, und alle haben die folgende Lösung (Pseudocode) gefunden:
%Vor% Die Berechnungskomplexität für dieses Algo ist n(n-1)/2 . (Wir sind in der High School, und wir haben nicht über Big-O gesprochen, aber es scheint O(n^2) zu sein). Diese Lösung erscheint hässlich und natürlich langsam, also habe ich versucht, etwas schneller zu programmieren:
Auf diese Weise enthält vS alle Elemente, die wir bereits bestanden haben. Wenn sich das Element v[i] in diesem Array befindet, ist es ein Duplikat und wird entfernt. Die Berechnungskomplexität für die binäre Suche ist log(n) und für die Hauptschleife (zweites Snippet) ist n . Daher ist das ganze CC n*log(n) wenn ich mich nicht irre.
Dann hatte ich eine andere Idee, einen binären Baum zu benutzen, aber ich kann ihn nicht ablegen Grundsätzlich sind meine Fragen:
Danke
Die einfachste Lösung besteht darin, das Array einfach zu sortieren (nimmt O (n log n) mit der Standardimplementierung, falls Sie sie verwenden können.) oder einen einfachen randomisierten Quicksort erstellen (der Code ist sogar auf Wikipedia)).
Danach scannen Sie es noch einmal. Während dieses Scans eliminieren Sie einfach aufeinanderfolgende identische Elemente.
Wenn Sie es in O (n) machen wollen, können Sie auch ein HashSet mit Elementen verwenden, die Sie bereits gesehen haben. Iterieren Sie einfach einmal über Ihr Array, überprüfen Sie für jedes Element, ob es sich in Ihrem HashSet befindet.
Wenn es nicht dort ist, füge es hinzu. Wenn es dort ist, entfernen Sie es aus dem Array.
Beachten Sie, dass dies zusätzlichen Speicher benötigt und das Hashing einen konstanten Faktor hat, der zu Ihrer Laufzeit beiträgt. Obwohl die Komplexität der Zeit besser ist, wird die praktische Laufzeit nur dann schneller sein, wenn Sie eine bestimmte Array-Größe überschreiten
Sie können oft einen Raum-Zeit-Kompromiss verwenden und mehr Speicherplatz investieren, um Zeit zu sparen.
In diesem Fall könnten Sie eine Hash-Tabelle verwenden, um die eindeutigen Wörter zu bestimmen.
add ist O(n) , Ihre CC-Berechnung ist also falsch. Dein Algorithmus ist O(n^2) .
Außerdem, wie wäre remove umzusetzen? Es sieht auch so aus, als wäre es O(n) - der ursprüngliche Algorithmus wäre also O(n^3) .
Tags und Links algorithm string complexity-theory big-o duplicates