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

Question

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 encloser 中的语句 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;
}

Usingisalpha可以帮助您解决问题评论中提到的问题，即使您的语言环境发生更改也可以使用。

Answer 2

当您谈论复杂性时，您是在谈论它根据输入的大小而增长了多少。在这种情况下，它基于作为str. 在 while 条件下检查的东西的数量不会改变。它被固定在算法中，即所谓的“常数因子”，所以我们不计算它。因为在最坏的情况下，测试对字符串的每个字符运行一次，它是O(n)，其中n是字符串的长度。