我将如何发现这段代码的时间和空间复杂性

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) = '';
                count+=checkPalin(palin, index);
            }
        }
        free(palin);
        index = 0;
        fwd++;
        len--;
    }
    printf("Palindromes: %dn", 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

对于时间复杂性，您的分析是正确的。它是O(n^2(，因为n+(n-1(+(n-2(++1个步骤。对于空间复杂性，通常只计算在任何给定时间所需的空间。在您的情况下，第一次通过循环时，您需要的最多额外内存是O(n(，因此空间复杂性是线性的。

也就是说，这不是检查回文的特别好的代码。您可以在O(n(时间和O(1(空间内完成这项工作，并且实际上可以启动更干净、更清晰的代码。

Gah：阅读不够仔细。正确答案在其他地方给出。