Javaの部分文字列（）の時間複雑度

Question

JavaのString#substring()メソッドの時間複雑度はどのくらいですか？ Javaの7の寿命内の更新6のよう

Answer 1

新しい答え

、substringの挙動はコピーを作成するように変更 - ので、すべてStringは、前述したように、他のオブジェクトと共有ないあるchar[]を指し、私が知っている限り。その時点で、substring()はO（n）操作になりました。ここでnは部分文字列内の数字です。

旧答え：前のJava 7

文書化されていない - しかし、あなたが想定した場合の練習O（1）は、ガベージコレクションが必要とされない、など

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

Answer 2

O（1）元の文字列のコピーが行われないため、オフセット情報の異なる新しいラッパーオブジェクトが作成されます。

Answer 3

次のように判断しますが、Javaのパフォーマンスの欠点は、文字列の部分文字列ではなく、どこかにあります。 コード：

public static void main(String[] args) throws IOException { 

     String longStr = "asjf97zcv.1jm2497z20`1829182oqiwure92874nvcxz,nvz.,xo" + 
       "aihf[oiefjkas';./.,z][p\\°°°°°°°°?!(*#&(@*&#!)^(*&(*&)(*&" + 
       "fasdznmcxzvvcxz,vc,mvczvcz,mvcz,mcvcxvc,mvcxcvcxvcxvcxvcx"; 
     int[] indices = new int[32 * 1024]; 
     int[] lengths = new int[indices.length]; 
     Random r = new Random(); 
     final int minLength = 6; 
     for (int i = 0; i < indices.length; ++i) 
     { 
      indices[i] = r.nextInt(longStr.length() - minLength); 
      lengths[i] = minLength + r.nextInt(longStr.length() - indices[i] - minLength); 
     } 

     long start = System.nanoTime(); 

     int avoidOptimization = 0; 
     for (int i = 0; i < indices.length; ++i) 
      //avoidOptimization += lengths[i]; //tested - this was cheap 
      avoidOptimization += longStr.substring(indices[i], 
        indices[i] + lengths[i]).length(); 

     long end = System.nanoTime(); 
     System.out.println("substring " + indices.length + " times"); 
     System.out.println("Sum of lengths of splits = " + avoidOptimization); 
     System.out.println("Elapsed " + (end - start)/1.0e6 + " ms"); 
    } 

出力：それはOである（1）またはそうでない場合

substring 32768 times 
Sum of lengths of splits = 1494414 
Elapsed 2.446679 ms

、依存しています。メモリ内の同じ文字列を参照している場合は、が非常にの長い文字列であると想像してください。長い文字列を参照して長い文字列を参照しないでください。長い間メモリを解放していいのではないでしょうか？

Answer 4

古いバージョンのJavaではO（1）でしたが、Jonが述べたように、同じ基本char []と異なるオフセットと長さの新しいStringが作成されました。

しかし、これは実際のchar []が除去された共有、オフセットおよび長さフィールドを除去したJava 7アップデート6

を開始変化しています。 substring（）はすべての文字を新しいStringにコピーするだけです。

エルゴ、サブストリングは今線形複雑度のJava 7アップデート6

Answer 5

にO（N）です。これは、部分文字列に対するメモリリークの問題を修正した後です。

Java 1.7.0_06から、String.substringは定数の代わりに線形の複雑さを持つことを覚えておいてください。