1


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

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

I gave it a shot and this what i think:
in main we have two while loops. The outer one runs over the entire length-1 of the string. Now here is the confusion, the inner while loop runs over the entire length first, then n-1, then n-2 etc for each iteration of the outer while loop. so does that mean our time complexity will be O(n(n-1)) = O(n^2-n) = O(n^2)? And for the space complexity initially i assign space for string length+1, then (length+1)-1, (length+1)-2 etc. so how can we find space complexity from this? For the checkPalin function its O(n/2).
i am preparing for interviews and would like to understand this concept.
Thank you

4

2 回答 2

2

For time complexity, your analysis is correct. It's O(n^2) because of the n+(n-1)+(n-2)+...+1 steps. For space complexity, you generally only count space needed at any given time. In your case, the most additional memory you ever need is O(n) the first time through the loop, so the space complexity is linear.

That said, this isn't especially good code for checking a palindrome. You could do it in O(n) time and O(1) space and actually have cleaner and clearer code to boot.

Gah: didn't read closely enough. The correct answer is given elsewhere.

于 2011-05-02T16:19:07.503 回答
2

Don't forget that each call to checkPalin (which you do each time through the inner loop of main) executes a loop index / 2 times inside checkPalin. Your computation of the time complexity of the algorithm is correct except for this. Since index gets as large as n, this adds another factor of n to the time complexity, giving O(n3).

As for space compexity, you allocate each time through the outer loop, but then free it. So the space complexity is O(n). (Note that O(n) == O(n/2). It's just the exponent and the form of the function that's important.)

于 2011-05-02T16:23:50.700 回答