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

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)？ 对于空间复杂度，最初我为字符串 length+1 分配空间，然后为 (length+1)-1、(length+1)-2 等分配空间。那么我们如何从中找到空间复杂度呢？ 对于 checkPalin 函数，其 O(n/2)。
我正在准备面试，想了解这个概念。
谢谢

Answer 1

不要忘记，每次调用 checkPalin（每次通过 main 的内部循环执行）都会在 checkPalin 内执行循环 index / 2 次。除此之外，您对算法时间复杂度的计算是正确的。由于 index 与 n 一样大，这会在时间复杂度上增加另一个 n 因素，得到 O(n^{3 sup>）。}

至于空间复杂性，您每次都通过外循环分配，然后释放它。所以空间复杂度是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：没有仔细阅读。正确答案在别处给出。