回文を見つけるために、この再帰関数を作成しました。
def palindrome(string):
print("palindrome called with:"+string)
if(len(string)<=3):
return string[0]==string[-1]
else:
res=palindrome(string[1:-1])
print("palindrome returned:"+str(res))
return res
私は今、このアルゴリズムの時間計算量を見つけました。私の質問は私のベースケースですよね？len <= 3はどれですか？これを、インターネット上のいたるところにあるフィボナッチと階乗アルゴリズムの古典的な例に関連付けることはできません。
はい、事実はあなたのベースケースだけが正しいということです。
したがって、ここで行う必要があるのは、最初と最後の文字が同じであるかどうかを確認してから、残りの文字列も回文であるかどうかを確認することです。しかし、どの時点でもそれをチェックしていません。
したがって、コードの変更を最小限に抑えれば、次の解決策が機能します。空の文字列が引数として渡された場合、これは失敗します。
def palindrome(string):
print("palindrome called with:"+string)
if(len(string)<=3):
return string[0]==string[-1]
else:
if string[0] == string[-1]:
res=palindrome(string[1:-1])
print("palindrome returned:"+str(res))
return res
else:
return False
間違いなく、これを書くためのより良い方法があります。
def palindrome(s):
return s == '' or (s[0]==s[-1] and palindrome(s[1:-1]))
私が行ったのは、さらに2つの再帰呼び出しを行わせることで、基本ケースをさらに減らすことです。
さて、時間計算量になります。これは両方のコードで同じです。
1つの関数呼び出しでO(1)、最初と最後の文字を比較する操作を実行しています。そして、この再帰呼び出しはほとんどの場合行われていn/2ます。n/2なぜなら、長さの文字列ではn、各呼び出しで2文字を削除しているからです。したがって、全体的な複雑さは次のようになりO(n)ます（これは、すべての再帰呼び出しで文字列のコピー/スライスを無視することに注意してください）。
最後に、すべての再帰呼び出しの前に（スライス時に）新しい文字列を作成するため、これを再帰的に回避する必要があります。
def palindrome(s):
def _palindrome(string, i, j):
if i >= j:
return True
return string[i] == string[j] and _palindrome(string, i + 1, j - 1)
return _palindrome(s, 0, len(s) - 1)
これは、すべての呼び出しでコピーを作成するわけではありません。したがって、これは間違いなくO(n)解決策です。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加