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

私はそれを試してみましたが、これは私が思うことです:
主に 2 つの 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).
私は面接の準備をしていて、この概念を理解したいと思っています。
ありがとうございました

4

2 に答える 2

2

index / 2checkPalin への各呼び出し (main の内側のループを介して毎回行う) は、 checkPalin 内でループ回を実行することを忘れないでください。これを除いて、アルゴリズムの時間計算量の計算は正しいです。indexは と同じ大きさになるのでn、これは時間の複雑さに別の要因を追加nし、O(n 3 ) を与えます。

スペースの複雑さについては、外側のループを介して毎回割り当てますが、解放します。したがって、空間の複雑さは O(n) です。(O(n) == O(n/2) であることに注意してください。重要なのは指数と関数の形式です。)

于 2011-05-02T16:23:50.700 に答える
2

時間の複雑さについては、分析は正しいです。n+(n-1)+(n-2)+...+1 ステップのため、O(n^2) です。スペースの複雑さについては、通常、特定の時点で必要なスペースのみをカウントします。あなたの場合、これまでに必要な最も多くの追加メモリは、ループを初めて通過するときに O(n) であるため、スペースの複雑さは線形です。

とはいえ、これは回文をチェックするのに特に適したコードではありません。O(n) 時間と O(1) スペースでそれを行うことができ、実際にはよりクリーンで明確なコードを起動できます。

Gah : よく読んでいませんでした。正解は別のところにあります。

于 2011-05-02T16:19:07.503 に答える