文字列を同等の数に、またはその逆に変換することの複雑さは何でしょうか？プログラミング言語によって変わりますか？
表面的には、文字列全体をトラバースして数値に変換する必要があるため、O（n）ですか、それとも型キャストが使用されていますか？
この疑問は、与えられた番号が回文であるかどうかをチェックするルーチンを書いているときに起こりました。1つのアプローチは、数値を基数（ここでは10）で除算し続け、桁を累積して、最後にそれらをまとめることです。例：309/10 = rem（9）、30/10 = rem（0）、3/10 = rem（3）。903を取得します。
私が取ったもう1つのアプローチは、この数値を文字列に変換することでした。文字列には分割、反転などのメンバー関数がたくさんあるため、コードははるかに短くクリーンになりましたが、これが最善の方法ですか？
数値文字列は、位置表記法でフォーマットされた数値です。そのため、数値をバイナリ形式に変換するには、各桁の値に基数の累乗を掛けた値を考慮する必要があります。
ええ、これは O(N) 演算です。桁数が増えると実行時間が直線的に増加するからです。ただし、実際には、言語がサポートする数値データ型 (int32_t、int64_t など) によって N が制限される場合があります。しかし、任意精度の数値型が使用されている場合 (Python などの一部の言語ではデフォルトで使用されています)、桁数に制限はありません (明らかに使用可能なメモリを除いて)。
数値に変換するには、常にすべての桁を読み取る必要があります。だから、少なくともO(n)です。
今（疑似コード）のようなことをしています
a = 0
foreach digit in string
do
a = 10 * a + digit
end
ですO(n)。したがって、複雑さはO(n)
C＃およびC / C ++には、（可能な）数値を表す文字列に特別な情報はありません。したがって、変換時に文字列を1桁ずつ解析する必要があります。
ただし、桁数には制限があるため、O（1）だけが得られます。変換時間は制限されます（通常、最大数の変換によって）。32ビット整数の場合、変換では最大10桁の10進数（および場合によっては符号）を考慮する必要があります。
文字列からの変換も実際にはO（1）です。これは、文字列の解析中に、制限された文字数（32ビットintの場合は10 + 1）のみを考慮するだけで十分だからです。
厳密に言えば、Ointの最大値には制限があるため、intから文字列への変換の場合に-notationを使用することはできません。とにかく、（両方向の）変換に必要な時間は定数によって制限されます。
@Charlesが示唆しているように、他の言語（Python）は実際には任意精度の数値を使用できます。このような数値を解析する場合、時間はO(number of digits)、でO(string length)ありO(log(number))、両方の変換でそれぞれです。任意精度の数値では、両方の変換ですべての桁を考慮する必要があるため、これを高速化することはできません。精度が制限された数値との間の変換についても、同じO(1)理由が当てはまります。ただし、Pythonでの解析のプロファイルを自分で作成しなかったため、効率の低いアルゴリズムが使用されている可能性があります。
編集：@Steveの提案に従って、C / C ++およびC＃での解析で最初の空白がスキップされることを確認したため、string->int変換の時間は実際にはO(input length)です。文字列がトリミングされていることがわかっている場合、変換は再び行われO(1)ます。
純粋な数値演算子 (C++ および C# では "%" モジュラス演算子になると思います) を扱うことは、正しくコーディングされていればより効率的であると確信しています。末尾が先頭と一致する)、文字列と数値の間の変換を実行すると、その変換を実行せずに同じことを実行できる場合にのみ、操作が複雑になります。
とはいえ、数値と文字列の間の変換によるパフォーマンスへの影響については心配しません。プログラムの他のほとんどの領域のパフォーマンスへの影響に比べれば、おそらく取るに足らないことだからです。数値型は 64 ビットに制限されているため、カスタム コーディングされた大きな数値型を実装/使用しない限り、とにかく解析する予定の桁数の上限が比較的低くなります。
複雑さが O(n) であることを心配する必要はありません。n は数値の大きさです。O(n) のようになります。ここで、n は桁数です (これは私が言及した低いキャップを持っています)、または (別の返信で述べたように) O(log(n)) は、n が数値の大きさの場合です。パフォーマンスへの影響は比較的重要ではありません。
あなたが示唆するように、Nに制限がない場合（2 GBのRAMでは最大20億桁の数値しか保存できないため、これは不可能です）、数学を実行するパフォーマンスについてもっと考える必要があるかもしれませんオペレーター。この大きな数値型に対する「%」および「/」演算子のパフォーマンスを考慮してください。ただし、数値を文字列に変換するために、基本的に同じ演算子を使用していることに注意してください。繰り返しますが、正しく処理すれば、数値として直接処理することに勝るものはありません。
数値 N を文字列に変換する場合。基数 10 の O(log(N)) が必要です (10 で割って余りを保持する場合) 長さ N の文字列を変換する場合、O(N) が必要です。(あなたの数に 10^(N)*digit(N) を追加し続けるアルゴリズムを使用する場合)
自分のものではない関数 (文字列など) を使用すると、それらの関数が遅くなることが予想されます。