Худший случай Сложность этого кода в 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).

Редактировать: Поцарапать это, он называет strlen тем временем цикла. Я собираюсь обновить его до O(n^2). Где n - длина pebbles. Было бы просто заставить это вернуться к O(n). Вызовите strlen() один раз и запишите значение.