-1 
int foo(char *str)
{
    char *p = str;
    while (p && *p!='\0' && 
        ((*p >= 'a' && *p <= 'z') 
            || (*p >= 'A' && *p <= 'Z') || *p == '@')) {
         p++;
    }
    return p-str;
}

上記の複雑なwhileステートメントの時間と空間の複雑さはどうなりますか。while 囲みのステートメントの数に依存しますか while (p && *p!='\0' && ((*p >= 'a' && *p <= 'z') || (*p >= 'A' && *p <= 'Z') || *p == '@'))

またはwhile本体のみ

while(){ 
 //body statements   
  p++;
}

上記のように。&&また、またはの短絡にも依存し||ます。

4

2 に答える 2

1

ランタイムまたはスペースの複雑さについてはわかりませんが、実際の条件の複雑さは、読みやすくするためにかなり単純化できます。まず、pループごとにポインターをチェックする必要はありませんstr。最初に別のチェックで null 以外のポインターであることを確認してください。次にisalpha、文字のチェックに使用する必要があります。

したがって、コードは代わりに次のようになります。

int foo(char *str)
{
    if (str == NULL)
        return 0;

    char *p = str;
    while (*p != '\0' && (isalpha(*p) || *p == '@'))
        p++;

    return p - str;
}

を使用isalphaすると、質問へのコメントに記載されている問題を解決するのに役立ち、ロケールが変更された場合でも機能します。

于 2012-09-03T06:44:35.277 に答える
0

複雑さについて話すときは、入力のサイズに基づいてどれだけ複雑になるかについて話します。この場合、これはとして渡された文字列のサイズに基づいていstrます。while条件でチェックされるものの数は変わりません。これは、いわゆる「定数係数」と呼ばれるアルゴリズムに固定されているため、カウントしません。最悪の場合、テストは文字列の各文字に対して1回実行されるため、はですO(n)。ここnで、は文字列の長さです。

于 2012-09-03T04:00:38.257 に答える