Как бы я нашел время и пространство сложность этого кода?

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) выполняет цикл index / 2 раз внутри checkPalin. Ваше вычисление временной сложности алгоритма является правильным, за исключением этого. Поскольку 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), и у вас действительно будет более чистый и понятный код для загрузки.

Гах : недостаточно внимательно прочитал. Правильный ответ дан в другом месте.