Ich wurde nach einer Interviewfrage gefragt, um die Anzahl der eindeutigen absoluten Werte unter den Elementen des Arrays zu finden. Ich kam zu der folgenden Lösung (in C ++), aber der Interviewer war nicht zufrieden mit der Laufzeit-Effizienz des Codes.
for Schleife führt A.size() mal aus. Ich bin mir jedoch nicht sicher über die Effizienz von STL std::find (Im schlimmsten Fall könnte es% sein co_de%, das macht diesen Code O(n) ? Code ist:
%Vor% std::find() ist linear (O (n)). Ich würde einen sortierten assoziativen Container verwenden, um dies zu handhaben, insbesondere std :: set .
Bei diesem Ansatz gibt es immer noch einen gewissen Zeitaufwand für die Laufzeit. Die Verwendung eines separaten Containers verursacht die Kosten dynamischer Zuordnungen, wenn die Containergröße zunimmt. Sie könnten dies an Ort und Stelle tun und diese Strafe nicht auftreten, aber mit Code auf dieser Ebene ist es manchmal besser, klar und explizit zu sein und den Optimierer (im Compiler) arbeiten zu lassen.
Um alternativen Code zu dem gesetzten Code vorzuschlagen.
Beachten Sie, dass wir den Vektor des Aufrufers nicht ändern möchten. Es ist besser, den Compiler für uns kopieren zu lassen, als unser eigenes zu erstellen. Wenn es in Ordnung ist, ihren Wert zu zerstören, können wir eine nicht konstante Referenz verwenden.
%Vor% Der Vorteil hier ist, dass wir nur einmal zuordnen / kopieren, wenn wir uns für Wert entscheiden, und der Rest ist alles in-Place, während Sie immer noch eine durchschnittliche Komplexität von O(n log n) auf die Größe von v haben.
Ja, das ist O (N 2 ) - Sie werden mit einer linearen Suche für jedes Element enden.
Eine einigermaßen naheliegende Alternative wäre die Verwendung von std::set oder std::unordered_set . Wenn Sie kein C ++ 0x haben, können Sie std::unordered_set durch tr1::unordered_set oder boost::unordered_set ersetzen.
Jede Einfügung in std::set ist O (log N), also ist Ihre Gesamtkomplexität O (N log N).
Bei unsordered_set hat jede Einfügung eine konstante (erwartete) Komplexität, die insgesamt eine lineare Komplexität ergibt.
Ersetzen Sie im Prinzip Ihre std :: list durch ein std :: set. Dies gibt Ihnen O (log (set.size ())) Suchen + O (1) Einfügungen, wenn Sie die Dinge richtig machen. Aus Effizienzgründen ist es auch sinnvoll, das Ergebnis von abs (* it) zu cachen, obwohl dies nur einen minimalen (vernachlässigbaren) Effekt hat. Die Effizienz dieser Methode ist ungefähr so gut, wie Sie es bekommen können, ohne einen wirklich guten Hash zu verwenden (std :: set verwendet Bin-Bäume) oder mehr Informationen über die Werte im Vektor.
Da ich mit der vorherigen Antwort nicht glücklich war, gehört mir heute. Deine ursprüngliche Frage erwähnt nicht, wie groß dein Vektor ist. Angenommen, Ihr std::vector<> ist extrem groß und enthält sehr wenige Duplikate (warum nicht?). Dies bedeutet, dass die Verwendung eines anderen Containers (z. B. std::set<> ) im Grunde Ihren Speicherverbrauch verdoppelt. Warum sollten Sie das tun, da Ihr Ziel einfach darin besteht, nicht doppelt zu zählen?
Ich mag @Flame antwort, aber ich war nicht wirklich glücklich mit dem Aufruf std::unique . Sie haben viel Zeit damit verbracht, Ihren Vektor sorgfältig zu sortieren und dann das sortierte Array einfach zu verwerfen, während Sie es später wiederverwenden könnten.
Ich konnte in der STD-Bibliothek nichts wirklich Elegantes finden, daher hier mein Vorschlag (eine Mischung aus std::transform + std::abs + std :: sort , aber ohne danach das sortierte Array zu berühren."
Bonuspunkt funktioniert mit Vorwärtsiterator:
%Vor%Zwei Punkte.
std :: list ist sehr schlecht für die Suche. Jede Suche ist O (n).
Verwenden Sie std :: set. Einfügen ist logarithmisch, entfernt Duplikate und ist sortiert. Fügen Sie jeden Wert O (n log n) ein und verwenden Sie dann set :: size, um die Anzahl der Werte zu finden.
Um Teil 2 Ihrer Frage zu beantworten, ist im C ++ - Standard der Worst-Case für Operationen mit Containern und Algorithmen vorgeschrieben.
Finden : Da Sie die freie Funktionsversion von find verwenden, die Iteratoren akzeptiert, kann sie nichts annehmen über die in der Reihenfolge übergeben, kann es nicht davon ausgehen, dass der Bereich sortiert ist, so muss es jeden Artikel durchlaufen, bis es eine Übereinstimmung findet, die O (n) ist.
Wenn Sie andererseits set :: find verwenden, kann dieser Mitgliederfund verwendet werden Die Struktur der Menge und ihre Leistung muss O sein (log N), wobei N die Größe der Menge ist.
Um Ihre zweite Frage zuerst zu beantworten, ist der Code O(n^2) , weil die Komplexität von find O(n) ist.
Sie haben Optionen, um es zu verbessern. Wenn der Zahlenbereich niedrig ist, können Sie einfach ein ausreichend großes Array einrichten und die Anzahl erhöhen, während Sie über die Quelldaten iterieren. Wenn der Bereich größer aber spärlich ist, können Sie eine Hash-Tabelle verwenden, um die Zählung durchzuführen. Beide Optionen sind lineare Komplexität.
Andernfalls würde ich eine Iteration machen, um den abs-Wert jedes Elements zu nehmen, sie dann zu sortieren und dann die Aggregation in einem einzigen zusätzlichen Durchlauf durchzuführen. Die Komplexität hier ist n log(n) für die Sortierung. Die anderen Durchgänge sind für die Komplexität nicht wichtig.
Wie @Jerry sagte, um das Thema der meisten anderen Antworten ein wenig zu verbessern, könnten Sie anstelle von std :: map oder std :: set eine std :: unordered_map oder std :: unordered_set (oder das Boost-Äquivalent).
Dies würde die Laufzeiten von O (n lg n) oder O (n) verringern.
Eine andere Möglichkeit, abhängig von der Bandbreite der gegebenen Daten, könnte eine Variante der Radix-Sortierung sein, obwohl es nichts in der Frage gibt, das dies sofort vermuten lässt.
Sortieren Sie die Liste mit einer Radix-Stilsortierung nach O (n) ish-Effizienz. Vergleichen Sie benachbarte Werte.
Am besten passen Sie den Quicksort-Algorithmus so an, dass wir bei der Partitionierung immer dann zwei gleiche Elemente erhalten, dann das zweite Duplikat mit dem letzten Element im Bereich überschreiben und dann den Bereich verkleinern. Dadurch wird sichergestellt, dass doppelte Elemente nicht doppelt verarbeitet werden. Auch nach der schnellen Sortierung ist der Bereich des Elements die Antwort Die Komplexität ist immer noch O (n * Lg-n), aber dies sollte mindestens zwei Durchläufe über das Array speichern.
Auch die Einsparungen sind proportional zu% der Duplikate. Stellen Sie sich vor, wenn sie die ursprüngliche Frage verdrehen, sagen wir, 90% der Elemente sind doppelt vorhanden ...
Noch ein Ansatz:
Platzsparend: Verwenden Sie eine Hash-Map. O (logN) * O (n) für die Einfügung und einfach die Anzahl der Anzahl der erfolgreich eingefügten Elemente beibehalten.
Zeiteffizient: Verwenden Sie die Hashtabelle O (n) für die Einfügung und behalten Sie einfach die Anzahl der erfolgreich eingefügten Elemente.
Sie haben Schleifen in Ihrem Code verschachtelt. Wenn Sie jedes Element über das gesamte Array scannen, erhalten Sie eine Komplexität von O (n ^ 2), die in den meisten Szenarien nicht akzeptabel ist. Das war der Grund für die Merge Sort und Quick-Sort -Algorithmen kamen, um Verarbeitungszyklen und Maschinenaufwand zu sparen. Ich werde vorschlagen, dass Sie die vorgeschlagenen Links durchgehen und Ihr Programm neu gestalten.
Tags und Links algorithm c++ performance