Konvertieren von string zu Zahl & vice versa Komplexität

Was wäre die Komplexität der Konvertierung von string in Ihre entsprechende Nummer, oder Umgekehrt? Ändert es je nach Programmiersprache?

Auf dem Gesicht, braucht man zum durchqueren die gesamte Zeichenfolge zu konvertieren, um eine Zahl, so ist es O(n), oder ist ein typecasting verwendet?

Dieser Zweifel entstand, als ich war das schreiben eine routine um zu überprüfen, ob eine gegebene Zahl ein Palindrom ist oder nicht. Ein Ansatz wäre, zu halten, teilen der Zahl durch die Basis (hier 10), häufen sich stellen, und legte Sie zusammen am Ende. Beispiel: 309/10=rem(9), 30/10=rem(0), 3/10=rem(3). wir bekommen 903.

Anderen Ansatz, den ich nahm war, wandelt diese Zahl in einen string, und da die Saiten haben eine Menge von member-Funktionen split, reverse usw., war der code viel kürzer und sauberer, aber ist das der beste Weg, dies zu tun?

  • Was sehen Sie als "N" in deinem Fall?
  • es gibt keine Obergrenze für die Größe von N...
  • OK, ich Frage anders: Bin ich zu Recht davon ausgehen, dass Sie sehen, N als Länge der Eingabe-string ein und fragt nach der algorithmischen Komplexität der Analyse, die Zeichenfolge in eine Zahl?
  • ja ttoni, du hast Recht...
InformationsquelleAutor Srikar Appalaraju | 2010-12-19
  1. 14

    Numerische strings sind formatierte zahlen im Stellenwertsystem - so der Wert der einzelnen Ziffer multipliziert mit einem Strom von der Basis muss berücksichtigt werden, um die Umwandlung der Zahl in einen Binär-format.

    Also ja, es ist eine O(N) operation, da die Laufzeit steigt Linear, da mehr Ziffern Hinzugefügt werden. Doch in der Praxis N kann begrenzt werden, indem beliebige numerische Daten-Typen der Sprache unterstützt (z.B. int32_t, int64_t). Aber wenn beliebiger Genauigkeit Anzahl Arten verwendet werden, (welche in einigen Sprachen, wie Python, verwenden Sie standardmäßig), dann gibt es keine Begrenzung für die Anzahl der Ziffern (anderen als der verfügbare Speicher natürlich).

    InformationsquelleAutor Charles Salvia
  2. 4

    Konvertieren in eine Zahl, die Sie immer Lesen Sie alle Ziffern. So ist es zumindest O(n).

    Nun etwas wie (pseudocode)

    a = 0
foreach digit in string
do
   a = 10 * a + digit
end

    Ist O(n). So ist die Komplexität O(n)

    • streng genommen, ist es falsch. für O(n) notation n müssen neigen bis unendlich.
    • N tendiert gegen unendlich, wenn beliebiger Genauigkeit-Nummern verwendet werden.
    • du hast Recht. So macht das Sinn, nur für die Sprachen, mit integrierten arbitrary-precision numbers (ausgenommen C/C++ und C#).
    • wer hat gesagt, die bigints werden muss "built-in"?
    • und @Vlad: aber für eine beliebige Präzision wird dies O(n^2) da die Berechnung der Multiplikation 10*a ist O(n) - operation.
    • der OP spricht über die built-in-Konvertierungen. Die built-in-Konvertierungen kann nicht Arbeit mit nicht-built-in-Typen. 😛

    InformationsquelleAutor Peter van der Heijden
  3. 0

    Wenn Sie konvertieren eine Zahl N in einen string. Es dauert O(log(N)) mit der Basis 10. (Wenn Sie durch 10 dividiert und halten den Rest)
    Wenn Sie konvertieren eine Zeichenfolge mit der Länge N, dann dauert es O(N). (Wenn Sie den Algorithmus verwenden whic hält hinzufügen, um Ihr die Zahl 10^(N)*Ziffer(N))

    Wenn Sie Funktionen verwenden, die nicht deine (sagen wir mal für string), können Sie nur erwarten, dass Sie langsamer sein.

    • Beide nehmen O(N), wobei N die Anzahl der Ziffern. Dies ist die richtige Art und Weise zu analysieren, arithmetische algorithmen.
    • Wenn die Anzahl N=10^5. Wie viele Schritte, um es in einen string konvertieren? Ich denke, O(log(N)), denn das ist die Anzahl der Ziffern.
    InformationsquelleAutor synepis
  4. 0

    Ich bin mir relativ sicher, dass der Umgang mit reinen numerischen Operatoren (in c++ und c# ich denke, es wäre das "%" modulo-operator) wird zu mehr Effizienz, wenn richtig codiert, weil auf einer bestimmten Ebene, die Sie haben zu prüfen, die für ähnliche Funktionen (ist das Ende entspricht dem Anfang) und durchführen einer Umwandlung zwischen string und Zahl kann nur hinzufügen, um die Komplexität von der operation, wenn Sie dasselbe tun können, ohne, dass die Durchführung der Konvertierung.

    Sagte, ich würde nicht sorgen über die Auswirkungen auf die Leistung der Umwandlung zwischen zahlen und strings, da ist es wahrscheinlich unbedeutend im Vergleich zu den Auswirkungen auf die Leistung der meisten anderen Gebiete des Programms. Numerische Datentypen sind begrenzt auf 64 bits, wodurch sich eine relativ niedrige Obergrenze für die Anzahl der Ziffern, die Sie planen können, um zu analysieren, sowieso, es sei denn, Sie sind der Umsetzung/Verwendung von custom-coded große-Zahl-Typen.

    Brauchen Sie sich keine sorgen über die Komplexität als O(n) wobei n die Größenordnung der Zahl. Es wäre mehr wie O(n), wobei n die Anzahl der Ziffern (die hat den low-cap, die ich erwähnt) oder (wie bereits erwähnt in einer anderen Antwort) O(log(n)) wenn n die Größenordnung der Zahl. Relativ unbedeutende Auswirkungen auf die Leistung.

    Nun, wenn, wie Sie vorschlagen, Sie haben keine Begrenzung auf N (was nicht möglich ist, weil mit 2 GB RAM kannst du nur das speichern von Rufnummern mit bis zu 2 Milliarden stellen), dann haben wir vielleicht denken, dass mehr über die Leistung der darstellenden mathematischen Operatoren. Betrachten Sie die Leistung von "%" und " /" - operator auf diese große Anzahl geben. Aber dann erkennen, dass, um die Umwandlung der Zahl in einen string, es ist im Grunde mit denselben Betreiber sowieso. Wieder einmal, kann man nicht schlagen der Handhabung, da direkt eine Nummer wenn du es richtig machst.

    InformationsquelleAutor BlueMonkMN
  5. 0

    C# und C/C++ keine speziellen Informationen in die Saiten, das ist die (mögliche) numerischen Wert. Daher müssen Sie analysiert die Zeichenfolge Ziffer für Ziffer bei der Konvertierung.

    Jedoch die Anzahl der stellen begrenzt ist, so haben wir nur O(1): die Umstellung Zeit ist begrenzt (in der Regel durch die Umwandlung von der größten Zahl). Für eine 32-bit-int die Umwandlung hat zu berücksichtigen, maximal 10 Dezimalstellen haben (und eventuell ein Schild).

    Konvertierung von string ist eigentlich O(1), als auch, weil während der Analyse, es ist genug, nur auf einer begrenzten Anzahl von Zeichen (10+1 bei 32-bit int).

    Streng genommen, können wir nicht O-notation für den Fall von int-zu-string-Konvertierung, da der maximale Wert von int ist begrenzt. Trotzdem, die benötigte Zeit für die Konvertierung (in beide Richtungen) ist beschränkt durch eine Konstante.

    Wie @Charles schon sagt, andere Sprachen (Python -) tatsächlich können beliebige Genauigkeit zahlen. Für die Analyse solcher zahlen, die Zeit ist O(number of digits), die O(string length) und O(log(number)) für beide Umwandlungen, beziehungsweise. Mit beliebig genauer zahlen, man kann es nicht schneller, da für beide Konvertierungen jede Ziffer berücksichtigt werden müssen. Für die Umwandlungen zu/von einer begrenzten Genauigkeit zahlen, die gleichen O(1) Argumentation gilt. Allerdings habe ich nicht Profil das parsing in Python selbst, also vielleicht einen weniger effizienten Algorithmus, der es verwendet wird.

    EDIT: nach dem @Steve Vorschlag, ich habe das parsing in C/C++ und C# überspringt die ersten whitespace-Zeichen, also die Zeit, die für string->int Konvertierung ist eigentlich O(input length). Im Falle es ist bekannt, dass sich der string getrimmt ist, wird die Umwandlung wieder O(1).

    • Natürlich können wir verwenden big-O-notation erhalten wir nur O(1), wenn Sie nicht mit bigints.
    • Ich spreche explizit über C/C++ und C#, die nicht gebaut haben,-in bigints.
    • für eine beliebige Präzision, es ist O((Anzahl der Ziffern)^2), siehe auch den Kommentar zu @Peters Antwort.
    • Ich sehe nicht, warum es stimmt. Nach allem, es hängt von der internen Darstellung der bigints. Wenn bigints bestehen aus mehreren Blöcken (entsprechend der Darstellung N = n_0 + 10^kn_1 + 10^2kn_2 etc.), die Multiplikation mit 10 ist sehr effizient. Hast du die Messung der Leistungsfähigkeit von parsing in Python?
    • wenn du redest über eine solche Umwandlung, die Sie in der Regel davon ausgehen, dass die Basis der string (10) unterscheidet sich von der Basis durch die interne Darstellung. Ansonsten ist es möglich, die O(1). Ad sprechen wir über Komplexität, nicht die Leistung.
    • Ich würde persönlich wählen Sie eine interne Darstellung, die es ermöglicht, die typischen Operationen, um schnell zu laufen (auch Einbußen bei der mehrere bits). Parsen ist definitiv einer der solche Operationen. So, hast du testen Sie die Python-die Leistung selbst, oder haben Sie eine andere Quelle von Informationen?
    • Was Sie sagen ist, dass Sie es vorziehen, zu vermeiden, die Umwandlung durch die Aufbewahrung der dezimal-string selbst... Naja, ich bin sicher, das ist, was getan wurde, in einigen Fällen, aber es ist eine Art mogeln bei der Beantwortung dieser Frage. Ich glaube nicht, die python verwenden, aber einige Anwendungen (z.B. GIMPS) verwenden müssen binäre Darstellung, so dass es die Komplexität der tatsächlichen Umsetzung ist interessant.
    • nicht notwendig ist die dezimale Darstellung. Sie können die store-Stücke, die Werte im Intervall 0..10^10-1 (passt in einen 32-bit int. Anyway, der OP fragt nicht theoretische minimum (was besser zu sein scheint, mit meiner Darstellung), aber über die eigentliche Leistung der Sprache.
    • genug, um nur einem begrenzten Anzahl von Zeichen" - es sei denn, Ihre conversion-überspringt die ersten whitespace-Zeichen 😉
    • gut, das ist wahr. Also, für C (sscanf) die Leistung ist O(string-Länge). 🙁
    • sicher, aber ich war meist zu scherzen. O(Anzahl der vorangestellte Leerzeichen in der Zeichenfolge + Konstante) ist immer noch O(1) solange die Eingabe keine Leerzeichen zu überspringen. Wenn die Eingabe nicht haben, Leerzeichen zu überspringen, dann ist das notwendigerweise eine lineare Komplexität der Bedienung, ob wir es tun oder unsere Anrufer ist. Also überspringen whitespace nicht wirklich "Kosten" jeder, der eine Komplexität, die nur verschiebt es, um uns von unserer Anrufer.
    • naja, aber theoretisch ist dies in der Tat macht die Leistung O(string size). Praktisch, es ist ein schöner Anwendungsfall des getrimmten strings 🙂
    • und in der Theorie ist die theoretische Leistung, die zählt, aber in der Praxis ist es die praktische Leistung 🙂
    • und für die OP ' s der Fall, können wir sicher sein, dass es keine führenden Leerzeichen, da die Zeichenfolge ist, die durch die Umwandlung von der Nummer.

    InformationsquelleAutor Vlad
Schreibe einen Kommentar