[解決済み] Java の substring() の時間複雑性

質問

の時間的複雑性はどの程度でしょうか？ String#substring() メソッドをJavaで作成できますか？

どのように解決するのですか？

新しい回答

Java 7 のライフタイム内のアップデート 6 の時点で、以下のような挙動になります。 substring はコピーを作成するように変更されました - したがって、すべての String を参照しています。 char[] である。 ではない は、私が知る限り、他のオブジェクトと共有されています。ですからその時点で substring() はO(n)演算となり、nは部分文字列の数字となります。

古い答え：Java 7以前

文書化されていませんが、ガベージコレクションが必要ないなどと仮定すれば、実際にはO(1)です。

これは、単に新しい String オブジェクトを参照し、同じ基礎となる char[] が、オフセットとカウントの値が異なる。つまり、コストは検証を行い、1つの新しい（適度に小さい）オブジェクトを構築するのにかかる時間ということになります。これは、ガベージコレクションやCPUキャッシュなどに基づいて時間が変化し得る操作の複雑さについて話すことが賢明である限り、O(1)です。特に、元の文字列や部分文字列の長さには直接依存しません。