Блог

У меня возникли трудности с поиском пространственной и временной сложности для этого кода, который я написал, чтобы найти количество палиндромов в строке.

 /**
 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 resu<
}

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

Я попробовал и вот что я думаю:

в main у нас есть два цикла 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) .
я готовлюсь к собеседованиям и хотел бы понять эту концепцию.
Спасибо

Не забывайте, что каждый вызов checkPalin (который вы выполняете каждый раз через внутренний цикл main) index / 2 раз выполняет цикл внутри checkPalin. Ваши вычисления временной сложности алгоритма верны, за исключением этого. Поскольку index становится таким большим, как n , это добавляет еще один коэффициент n к временной сложности, давая O (n³).

Что касается сложности пространства, вы выделяете каждый раз через внешний цикл, но затем освобождаете его. Итак, пространственная сложность равна O (n). (Обратите внимание, что O (n) == O (n / 2). Важен только показатель степени и форма функции.)

Что касается временной сложности, то ваш анализ верен. Это O (n ^ 2) из-за n (n-1) (n-2) … 1 шагов. Для пространственной сложности обычно учитывается только пространство, необходимое в любой момент времени. В вашем случае самая большая дополнительная память, которая вам когда-либо требовалась, — это O (n) при первом прохождении цикла, поэтому пространственная сложность линейна.

Тем не менее, это не особенно хороший код для проверки палиндрома. Вы могли бы сделать это за O (n) времени и O (1) пространства и фактически получить более чистый и понятный код для загрузки.

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