javaのlastIndexOfの時間複雑度はどのくらいですか？

Question

Stringでそれを使用するためのJavaのlastIndexOfの時間の複雑さは何ですか？仮定 ：sいくつかStringとcあるint t= s.lastIndexOf(c); とすぐchar配列は、それがO（N）であるように文字列が実装されているように

Answer 1

s.charAt(0)あります。 O(n) -

public int lastIndexOf(int ch, int fromIndex) { 
    if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) { 
     // handle most cases here (ch is a BMP code point or a 
     // negative value (invalid code point)) 
     final char[] value = this.value; 
     int i = Math.min(fromIndex, value.length - 1); 
     for (; i >= 0; i--) { 
      if (value[i] == ch) { 
       return i; 
      } 
     } 
     return -1; 
    } else { 
     return lastIndexOfSupplementary(ch, fromIndex); 
    } 
} 

Answer 2

はString.lastIndexOf(int)にとっては線形です。

少なくとも、文字シーケンス全体を反復処理し、終了する必要があります。

これがJavaの機能です。

最悪の場合："abbbbbbbbbb".lastIndexOf('a')

String.lastIndexOf(String)のために、それはnが入力長さであり、mは、パラメータ長であるO(n*m)です。

この場合、Javaはstartを終了するまで繰り返し、針の最後の文字に一致する部分があれば、先行する文字と両側の文字を一致させようとします。

Answer 3

このメソッドの実装を見てください。両方のコードブランチでは、文字列の内部配列に対する単純な反復処理を含む：

int i = Math.min(fromIndex, value.length - 1); 
for (; i >= 0; i--) { 
     if (value[i] == ch) { 
      return i; 
     } 
} 

したがって複雑さだけO(n)、すなわち線形です。