アルゴリズムの時間計算量を計算する方法を学んでいます。ループを含む単純なアルゴリズムの時間計算量を計算することはできますが、再帰を使用するアルゴリズムの時間計算量を計算するのに問題があります。再帰的アルゴリズムの時間計算量を決定するのに助けが必要です。
問題の説明は次のとおりです。
2つの文字列SとTが与えられた場合、両方が空のテキストエディタに入力されたときに、それらが等しい場合に戻ります。＃はバックスペース文字を意味します。
例1：
入力：S = "ab＃c"、T = "ad＃c"出力：true説明：SとTの両方が "ac"になります。
例2：
入力：S = "ab ##"、T = "c＃d＃"出力：true説明：SとTの両方が ""になります。
例3：
入力：S = "a ## c"、T = "＃a＃c"出力：true説明：SとTの両方が "c"になります。
そして、私が開発したアルゴリズムは次のとおりです。
public boolean backspaceCompare(String S, String T) {
return removeAndDelete(S).equals(removeAndDelete(T));
}
public String removeAndDelete(String input){
int index = input.indexOf('#');
if(index==-1)
return input;
else if(index == 0)
return removeAndDelete(input.substring(index+1));
else
return removeAndDelete(input.substring(0,index-1)+input.substring(index+1));
}
次に、アルゴリズムの時間計算量を計算したいと思います。私を助けてください...
複雑さは2次式です。ましょN入力文字列の長さ。再帰呼び出しの数は#、入力の文字数と同じですO(N)。再帰呼び出しを行うたびに、部分文字列操作にがかかるO(N)ため、上限はO(N^2)。になります。のような入力を使用するaaaa####と、複雑さが少なくともO(N^2)、であることが簡単にわかります。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加