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

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

我试了一下，这是我的想法:
在 main 中，我们有两个 while 循环。外层的遍历字符串的整个 length-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)。
我正在准备面试，想了解这个概念。
谢谢

Answer 1

不要忘记每次调用 checkPalin(每次通过 main 的内部循环执行)都会执行一个循环 index / 2 checkPalin 里面的时间。除此之外，您对算法时间复杂度的计算是正确的。自 index变得和n一样大，这增加了另一个因素 n时间复杂度为 O(n³)。

至于空间复杂性，您每次都通过外循环进行分配，然后释放它。所以空间复杂度是O(n)。 (注意 O(n) == O(n/2)。重要的只是指数和函数的形式。)