c - 复杂 while 语句的时间和空间复杂度

Question

这个问题不太可能对任何 future 的访客有帮助；它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关，通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用， visit the help center 。

已关闭 10 年前。

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

如上所述。还取决于&&的短路吗？或|| .

Answer 1

我不知道你的运行时或空间复杂度，但实际条件复杂度可以大大简化以使其更具可读性。首先，您不必在每个循环中检查指针 p，首先在单独的检查中检查 str 是否为非空指针。其次你应该使用 isalpha检查字母。

因此代码可能如下所示:

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

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

    return p - str;
}

使用 isalpha 可以帮助您解决问题注释中指出的问题，并且即使您的区域设置发生更改也可以正常工作。