我如何找到这段代码的时间和空间复杂性？

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; 
} 

我给它一个镜头，这就是我想：
主，我们有两个while循环。外部字符串在字符串的整个长度-1上运行。现在这里是混淆，内部while循环首先遍历整个长度，然后是n-1，然后是n-2等，用于外部while循环的每次迭代。那么这意味着我们的时间复杂度将是O(n(n-1)) = O(n^2-n) = O(n^2)？ 而对于空间复杂性，最初我给字符串长度+1分配空间，然后（长度+ 1）-1，（长度+1）-2等，所以我们如何从中找到空间复杂度？ 对于checkPalin函数，它的O(n/2)。
我正在准备面试，并想了解这个概念。
谢谢

Answer 1

不要忘记，每次调用checkPalin（每次通过main内部循环执行操作）都会在checkPalin中执行循环index/2次。除此之外，您对算法时间复杂性的计算是正确的。由于index变得大到n，这增加了另一个因素n与时间复杂度，给出了O（n ）。

至于空间强度，你分配每次通过外部循环，但然后释放它。所以空间复杂度是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：没有仔细阅读。其他地方给出了正确的答案。