迴文遞歸算法的時間複雜度

Question

我已經寫了這個遞歸函數來尋找回文。

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？ 我無法將此與斐波那契和因子算法的經典示例相關聯，這些算法在互聯網上隨處可見。

Answer 1

是的，事實是，只有您的基本情況是正確的。

所以你應該在這裏做的是，檢查第一個和最後一個字符是否相同，然後檢查剩餘字符串是否也是迴文。 但在任何時候你都在檢查。

因此，如果您的代碼變化很小，那麼下面的解決方案將會起作用，如果將空字符串作爲參數傳遞，這將失敗。

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])) 

我所做的是，進一步降低你的基本情況，通過讓它使兩個遞歸調用。

現在，來到時間複雜度，這兩個代碼相同。

在一次函數調用中，我們正在做一個比較第一個字符和最後一個字符的操作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)解決方案。