회문 재귀 알고리즘의 시간 compxity

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입니까? 인터넷상의 모든 곳에있는 fibonacci 및 계승 알고리즘의 고전적인 예와 연결할 수 없습니다.

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자를 제거하기 때문입니다. 그러므로 전체적인 복잡성은 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) 솔루션입니다.