이 코드의 시간과 공간의 복잡성을 어떻게 알 수 있습니까?

Question

문자열에서 문장의 수를 찾기 위해 작성한이 코드의 공간과 시간 복잡성을 찾는 데 어려움이 있습니다.

/** 
This program finds palindromes in a string. 
*/ 

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

int checkPalin(char *str, int len) 
{ 
    int result = 0, loop; 

    for (loop = 0; loop < len/2; loop++) 
    { 

     if (*(str+loop) == *(str+((len - 1) - loop))) 
      result = 1; 
     else { 
      result = 0; 
      break; 
     } 
    } 

    return result; 
} 

int main() 
{ 
    char *string = "baaab4"; 
    char *a, *palin; 

    int len = strlen(string), index = 0, fwd=0, count=0, LEN; 
    LEN = len; 

    while(fwd < (LEN-1)) 
    { 
     a = string+fwd; 
     palin = (char*)malloc((len+1)*sizeof(char));  

     while(index<len) 
     { 
      sprintf(palin+index, "%c",*a); 
      index++; 
      a++; 

      if (index > 1) { 
       *(palin+index) = '\0'; 
       count+=checkPalin(palin, index); 
      } 
     } 

     free(palin); 
     index = 0; 
     fwd++; 
     len--; 
    } 

    printf("Palindromes: %d\n", count); 
    return 0; 
} 

나는 그것에게 기회를주고, 내가 무슨 생각이 :
을 주에 우리는 두 동안 루프를 가지고있다. 바깥 쪽은 문자열의 전체 길이 -1에 걸쳐 있습니다. 이제 혼란이 있습니다. inner while 루프가 먼저 전체 길이에 걸쳐 실행되고, 그 다음에 n-1, then-2 등이 실행됩니다. 그렇다면 우리의 시간 복잡성은 O(n(n-1)) = O(n^2-n) = O(n^2)일까요? 그리고 공간의 복잡성에 대해 처음에는 문자열 길이 +1, 그 다음 (길이 +1) -1, (길이 +1) -2 등의 공간을 할당합니다. 어떻게 공간 복잡성을 찾을 수 있습니까? checkPalin 함수의 경우 O(n/2)입니다.
나는 인터뷰를 준비 중이며이 개념을 이해하고자합니다.
감사합니다.

Answer 1

checkPalin을 호출 할 때마다 (메인의 내부 루프를 통해 매번) checkPalin 내에 루프 index/2 번을 실행한다는 것을 잊지 마십시오. 이것을 제외하고 알고리즘의 시간 복잡성 계산은 정확합니다. index은 n만큼 커지므로 시간 복잡도에 다른 요소 인 n이 추가되어 O (n)가됩니다.

공간 compexity에 대해서는 매번 외부 루프를 통해 할당하지만 해제하십시오. 그래서 공간의 복잡성은 O (n)입니다. O (n) == O (n/2)는 단지 지수와 중요한 함수 형식입니다.)

Answer 2

시간 복잡성에 대한 분석은 정확합니다. 그것은 n + (n-1) + (n-2) + ... + 1 단계 때문에 O (n^2)입니다. 공간의 복잡성 때문에 일반적으로 주어진 시간에 필요한 공간 만 계산합니다. 귀하의 경우에 가장 필요한 추가 메모리는 루프를 통해 처음으로 O (n)이므로 공간 복잡성은 선형입니다.

이것은 말하자면, 이것은 회문을 확인하는 데 특히 좋은 코드는 아닙니다. 당신은 O (n) 시간과 O (1) 공간에서 그것을 할 수 있었고 실제적으로보다 깨끗하고 명확한 코드를 부팅 할 수있었습니다.

gah : 자세히 읽지 않았습니다. 정답은 다른 곳에 주어진다.