이 알고리즘의 시간 복잡도가 기하 급수적 인 이유는 무엇입니까? 인터뷰하는 동안

Question

, 나는 다음과 같은 알고리즘의 시간 복잡도를 요청했다 : 그것은 단지되는 searchString의 길이를 통해 루프 나에게 나타나기 때문에

static bool SetContainsString(string searchString, HashSet<string> setOfStrings) 
{ 
    for (int i = 0; i < searchString.Length; i++) 
    { 
     var segment = searchString.Substring(0, i + 1); 

     if (setOfStrings.Contains(segment)) 
     { 
      var remainingSegment = searchString.Substring(segment.Length); 

      if (remainingSegment == "") return true; 
      return SetContainsString(remainingSegment, setOfStrings); 
     } 
    } 

    return false; 
} 

나는 "선형"대답했다. 예, 재귀 적입니다. 그러나 재귀 호출은 아직 반복되지 않은 문자열의 부분에만 있으므로 반복의 최종 결과는 문자열의 길이입니다.

나는 최악의 경우의 시간 복잡도가 기하 급수적이라고 내 인터뷰 담당자로부터 들었다.

누구든지 나를 명확히 할 수 있습니까? 내가 틀렸다면, 왜 그 이유를 이해해야합니다.

Answer 1

귀하의 면접 담당자가 여기에 잘못되었다고 생각합니다. 다음은 시간 복잡도가 지수가 아닌 이유에 대한 설명입니다.

• 각 함수 호출은 0 회 또는 1 회 재귀 호출 중 하나를 만듭니다.
• 각 재귀 호출은 문자열 길이를 적어도 하나 줄입니다.

O (n)에서 재귀 호출의 총 수를 제한합니다. 여기서 n은 입력 문자열의 길이입니다. 각각의 개별 재귀 호출은 다항식 작업량을 수행하므로 수행 된 전체 작업은 다항식입니다.

면접관이 혼란스러워하는 이유는 위의 코드는 문자열이 하나 이상의 단어로 분해 될 수 있는지 확인해야한다고 생각하기 때문에 모든 경우에 올바르게 작동하지 않습니다. 특히 재귀는 항상 낙관적으로 첫 접두사를 붙잡고 단어라는 것을 알게되고 그것이 무엇을 움켜 쥐고 있는지가 단어를 분리하는 올바른 방법이라고 가정합니다. 그러나 "사과 소스"와 같은 단어가 있다고 상상해보십시오. "a"를 풀어 재귀 적으로 "부관"을 만들려고한다면 "부풀리기"를 분해 할 방법이 없기 때문에이 단어가 화합물이 아니라고 잘못보고 할 것입니다. 이 문제를 해결하려면, 당신은 이런 식으로 재귀 호출을 변경해야 할 것 :

if (SetContainsString(...)) return true; 

이 방법을 잘못 분할을 선택하는 경우, 당신은 당신이 할 수있는 다른 가능한 분할을 확인로 이동합니다. 코드 의 변종은이 잠재적으로 동일한 하위 문자열을 여러 번 다시 방문 할 수 있기 때문에 최악의 경우 기하 급수적 인 시간이 걸리며 이는 내가 인터뷰하는 사람이 잘못 생각한 것이라고 생각합니다.