Javaの単純なアプリケーション複雑さ

Question

インタビューの問題を解決しなければならず、何かを理解できませんでした。 "ew ekil gnikih"のような文字列を "ハイキングが好き"のような文字列の場合、str.split（ ""）のような文字列を展開し、次に各単語を反転させる新しい文字列に追加します。 「 - 期待最悪の場合の時間計算量はO（N）である」 - 期待worsケースのスペースの複雑さをO（Nです ：のように、複雑さについて何かを求めていたがため

問題は、問題の最後にありました私は複雑な要求について何をすべき

public static String solution(String S){ 

    if(S.length()>1 && S.length()<200000){ 

     String toReturn = ""; 

     String[] splitted = null; 
     if(S.contains(" ")){ 
      splitted = S.split(" "); 
     } 
     else{ 
      splitted = new String[]{S}; 
     } 

     for(int i=0;i<=splitted.length-1;i++){ 
      String wordToChange = splitted[i]; 
      String reversedWord = ""; 
      for(int j=wordToChange.length()-1;j>=0;j--) 
       reversedWord+=wordToChange.charAt(j); 

      toReturn+=" " + reversedWord; 

     } 

     return toReturn.trim(); 

    } 
    return null; 
} 

：）（私はこのような問題を解決し、入力引数に必要なストレージ）

をカウントしませんか？ ありがとう！時間の複雑さについて

Answer 1

私はこの時のために正解はないと思う - あなたは最悪の場合には、「私はamtheone」とは、あなたが各文字の文字列を作成するような文字列があります少なくとも時間の複雑さ。

私の意見では、文字列の分割は、おそらくO（n）の複雑さになります。それは次の複雑さに追加するだけなので、それを忘れることができます。

これで空のStringを作成し、各Stringの上にcharを連結します。ここでは、この演算が配列（O（1））に値を挿入するのと同じくらい安価であると仮定しています。

この場合、メンバーメソッドconcat（）を使用して毎回新しいStringを作成すると仮定してください。 String.concat（String）の実装を調べる可能性がある場合、このメソッドはstring1.length + string2.lengthの長さに別のchar []を作成し、string1とstring2の両方をコピーしていることがわかりますそれにしたがって、この方法だけではO（n）の複雑さがあります。

n個の長さの単語に対してn個の文字を連結しているため、1単語に対してO（n *（n/2））= O（n^2）の複雑さを持ちます。 1単語の最悪の場合を仮定すると、O（n^2）という複雑さのクラスがあります。

あなたのコードでは、O（n）の空間複雑度クラスに同意します。しかし、これはJVMのインテリジェンスを前提としているため、あなたは未使用スペースです。

あなたのコードはうまくいくはずですが、私は本当にこの問題のコードが良くないと思います。あなたはStringBuilderを使ってそれを改善したり、char []の操作を直接行うことができます。

StringBuilderはVectorまたはArrayListと同じように機能するため、良いアイデアです。私は文字列よりもはるかに大きなchar []をバックグラウンドで処理しています。容量が（append（）メソッドを使用して）超過すると、以前のバッキング配列の2倍の大きさの配列が作成されます。これはO（nlogn）の時間複雑さにすぎないかもしれません。しかし、StringBuilderを初期のStringと同じサイズの容量で初期化することで、それをさらに調整することができます。つまり、バッキングchar []は容量を超えないため、まったくコピーされません。

private static void reverseCharArray(char[] result, int start, int end) { 
    int halfDifference = (end - start)/2; 
    for (int i = 0; i < halfDifference; i++) { 
     char buffer = result[start + i]; 
     result[start + i] = result[end - i - 1]; 
     result[end - i - 1] = buffer; 
    } 
}  

public static String reverseWordInString(String string) { 
    char[] stringAsCharArray = string.toCharArray(); 

    int indexStart = 0; 
    for (int indexEnd = 0; indexEnd < stringAsCharArray.length; indexEnd++) { 
     if (stringAsCharArray[indexEnd] != ' ') { 
      continue; 
     } 
     StringOperations.reverseCharArray(stringAsCharArray, indexStart, indexEnd); 
     indexStart = indexEnd + 1; 
    } 
    StringOperations.reverseCharArray(stringAsCharArray, indexStart, stringAsCharArray.length); 

    return String.valueOf(stringAsCharArray); 
} 

Answer 2

：

ワーストケースO（N）は、あなたが結果を得るために、N個の反復を計算した最悪のシナリオは、あなたのケースであなたに文字列を分割している必要があることを意味し（おそらくO（N）が必要ですが、split（）メソッドに依存します）、配列内の各Stringについて、文字列の終わりから始まり、文字を反転します。 だからあなたの最悪の場合はO（N）である+ O（N）... = O（N）スペースの複雑さについて

：

各文字列はオブジェクトであり、あなたが各列にメモリ内のスペースを確保しますここでは、文字列の配列を作成します。つまり、元の文字列から分割した単語または文字ごとにオブジェクトを作成します。 > O（N）

ホープ、これは明確にあなたの疑問