c编程语言代码的复杂性

Question

我想知道这段代码的复杂度是O(n)还是O(count*n)？我使参数计数，它不依赖于参数 n，如您所见：

void change(int A[], int n, int x)
{
  int i, j, count=0;
  for(i=0; i<n; i++)
  {
    if(A[i]==x)
     { count++; }
  }
  
  for(i=0; i<count; i++){
     for(j=0; j<n-i; j++){
         printf("Hello World"):
     }
  }
}

Answer 1

第一个循环是Theta(n)。第二个循环的时间复杂度（如您所见，取决于 count 的值）为：

T(n) = n + (n-1) + ... + (n-count) = O(n * count)

因此，最终时间复杂度为O(n * count)。而作为 count = O(n)，我们可以说时间复杂度是 O(n^2) n。