我如何找到這段代碼的時間和空間複雜性？

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：沒有仔細閱讀。其他地方給出了正確的答案。