此代码在C中的最差情况复杂度

Question

该函数采用代表鹅卵石的字符数组，并将数组重新排列为RED，WHITE和BLUE字符。 重新排列时进行的交换次数也会返回。 如果输入合法，并且成功重新排列 ，该函数返回1。如果在 输入中找到非法字符，它将返回0。

boolean processInput(char *pebbles, int *noOfSwaps){ 

    int low; 
    int mid; 
    int high; 

    *noOfSwaps = 0; 

    low = 0; 

    while (low < strlen(pebbles) && color(*(pebbles + low)) == RED) 
      low++; 

    high = strlen(pebbles) - 1; 

    while (high >= 0 && color(*(pebbles + high)) == BLUE) 
      high--; 

    mid = low; 

    while (mid <= high){ 

      if (color(*(pebbles + mid)) == RED){ 

        if (mid == low){ 

          low++; 
          mid++; 
        } 

        else{ 

          swap((pebbles + mid), (pebbles + low)); 

          (*noOfSwaps)++; 
          low++; 
          mid++; 
        } 
      } 

      else if (color(*(pebbles + mid)) == WHITE) 
        mid++; 

      else if (color(*(pebbles + mid)) == BLUE){ 
        if (color(*(pebbles + high)) == BLUE) 
          high--; 

        else{ 
          swap((pebbles + mid), (pebbles + high)); 
          (*noOfSwaps)++; 
          high--; 
        } 
      }  
      else 
        return 0; 
    } 
    return 1; 
} 

^^^上面有我的代码。只有一个功能。需要知道该功能的最坏情况复杂性和原因。谢谢！

Answer 1

当所有的鹅卵石都是红色的时，这条线至少会造成O(n) + O(color())。如果颜色是O(1)（这可能是），那么它只是O(n)：

while (low < strlen(pebbles) && color(pebbles[low]) == RED) 
    low++; 

的代码的其余部分似乎只是检查每个元素的颜色一次，所以这将是O(n) + O(color())为好。

所以我打算用O(n)。

编辑：从头开始，他在那个while循环中调用了strlen。我打算将其升级到O(n^2)。其中n是pebbles的长度。这很容易导致它回到O(n)。调用strlen()一次，并缓存该值。