此函数的时间复杂度/包括字符串数组

Question

为什么这个函数的时间复杂度是O((n^2)*L)(L-最大字符串的长度)而不是O(n^2)？ strcmp好像在玩什么，但不知道是什么。

void lex_sort(char *str_arr[]){
 int size = 0, i, j;
 while (str_arr[size] != NULL)
   size++;
 for (i = 0; i < size - 1; i++) {
   for (j = i + 1; j < size; j++) {
    if (strcmp(str_arr[i], str_arr[j]) > 0) {
    // str_arr[i] is greater than str_arr[j]
     char *temp = str_arr[i];
     str_arr[i] = str_arr[j];
     str_arr[j] = temp;
    }
   }
  }
 }

Answer 1

看起来 n = size 是数组中字符串的数量。你有两个循环，这使得它成为 O(n^2)。但是字符串的比较是O(L)。所以，你得到 O(n^2*L)。我想你已经明白了。 strcmp 是 O(L).

鲍比