algorithm - 我如何找到此代码的时间和空间复杂性？

我很难找到空间和时间复杂度的这段代码，我写了一个字符串中找到回文数。

/**
 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循环的每次迭代，内部while循环首先运行整个长度，然后是n-1，然后是n-2等那么这是否意味着我们的时间复杂度将是O(n(n-1)) = O(n^2-n) = O(n^2)？
对于空间复杂度，我最初为字符串长度+ 1，然后（长度+ 1）- 1，（长度+1）-2等指定空间，那么我们如何从中找到空间复杂度？
对于checkPalin函数，它的O(n/2)。
我正在准备面试，我想了解这个概念。
谢谢你

最佳答案

不要忘记每次调用checkpalin（每次通过main的内部循环执行）都会在checkpalin中执行循环index / 2次。除此之外，算法的时间复杂度的计算是正确的。由于index和n一样大，所以在时间复杂度上增加了n的另一个因素，给出了O（n3）。
至于空间压缩性，您每次通过外部循环分配，但然后释放它。空间复杂度为o（n）。（注意o（n）==o（n/2）。重要的是函数的指数和形式。）

关于algorithm - 我如何找到此代码的时间和空间复杂性？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5859456/