Diese Antwort bestimmt, ob zwei Zeichenfolgen Permutationen sind, indem sie deren Inhalt vergleichen. Wenn sie die gleiche Anzahl von jedem Zeichen enthalten, sind sie offensichtlich Permutationen. Dies wird in O (N) Zeit erreicht.
Ich mag die Antwort allerdings nicht, weil sie neu erfindet, was is_permutation tun soll . Das heißt, is_permutation hat eine Komplexität von:
höchstens O (N 2 ) Anwendungen des Prädikats, oder genau N , wenn die Sequenzen bereits gleich sind, wobei
N=std::distance(first1, last1)
Ich kann also die Verwendung von is_permutation nicht befürworten, wenn sie um Größenordnungen langsamer ist als ein handgesponnener Algorithmus. Aber sicherlich würde der Implementierer des Standards eine so offensichtliche Verbesserung nicht verpassen. Warum also is_permutation O (N 2 ) ?
Ich war es, der diese Antwort geschrieben hat.
Wenn die value_type der Zeichenfolge char ist, beträgt die Anzahl der in einer Nachschlagetabelle erforderlichen Elemente 256. Für eine Zwei-Byte-Codierung 65536. Bei einer Vier-Byte-Codierung hätte die Nachschlagetabelle etwas mehr als 4 Milliarden Einträge, mit einer wahrscheinlichen Größe von 16 GB! Und das meiste davon wäre ungenutzt.
Als Erstes müssen wir erkennen, dass selbst wenn wir die Typen auf char und wchar_t beschränken, dies immer noch nicht möglich ist. Genauso wenn wir is_permutation auf Sequenzen vom Typ int machen wollen.
Wir könnten eine Spezialisierung von std::is_permutation<> für ganzzahlige Typen der Größe 1 oder 2 Bytes haben. Aber das erinnert ein wenig an std::vector<bool> , was im Nachhinein nicht jeder für eine gute Idee hält.
Wir könnten auch eine Nachschlagetabelle verwenden, die auf std::map<T, size_t> basiert, aber dies ist wahrscheinlich schwer von der Zuweisung, sodass es möglicherweise kein Leistungsgewinn ist (oder zumindest nicht immer). Es könnte sich jedoch lohnen, einen für einen detaillierten Vergleich zu implementieren.
Zusammenfassend kann ich dem C ++ - Standard nicht vorwerfen, dass er keine Hochleistungsversion von is_permutation für char enthält. Erstens, weil ich in der realen Welt nicht sicher bin, dass es die gebräuchlichste Verwendung des Templates ist, und zweitens, weil die STL nicht das A und O aller Algorithmen ist, besonders dort, wo Domänenwissen verwendet werden kann, um die Berechnung für spezielle zu beschleunigen Fälle.
Wenn es sich herausstellt, dass is_permutation für char ziemlich wild ist, wären C ++ - Bibliotheksimplementierer in ihren Rechten, eine Spezialisierung dafür bereitzustellen.
Die von Ihnen zitierte Antwort funktioniert in char s. Es nimmt an, dass sie 8 Bit sind (nicht notwendigerweise der Fall) und so gibt es nur 256 Möglichkeiten für jeden Wert, und dass Sie billig von jedem Wert zu einem numerischen Index für eine Nachschlagetabelle von counts gehen können (für char in In diesem Fall sind der Wert und der Index identisch!)
Erzeugt eine Zählung, wie oft jeder char -Wert in jeder Zeichenfolge auftritt; Wenn diese Verteilungen für beide Strings gleich sind, sind die Strings Permutationen voneinander.
Was ist die zeitliche Komplexität?
Also ist die gesamte Zeitkomplexität O (N + M): linear, wie Sie beschreiben.
Nun macht std::is_permutation keine solchen Annahmen über seine Eingabe. Es weiß nicht, dass es nur 256 Möglichkeiten gibt, oder tatsächlich, dass sie überhaupt begrenzt sind. Es weiß nicht, wie man von einem Eingabewert zu einer Zahl wird, die es als Index verwenden kann, egal wie man das in konstanter Zeit macht. Das einzige, was es weiß, ist, wie man zwei Werte für Gleichheit vergleicht, weil der Anrufer diese Information liefert.
Also, die Komplexität der Zeit:
also wird die Komplexität bestenfalls quadratisch sein.
Tags und Links c++ permutation big-o standard-library string-comparison