c++ - 包含来自每个 k 列表的至少 1 个元素的最小元素范围的时间复杂度

Question

谁能详细说明这个函数的时间复杂度是多少 O(n^2 * k)？我知道 while 循环中的 for 循环最多会执行 k 次。但我不明白的是 n^2 项。

void findSmallestRange(int arr[][N], int n, int k)
{
  int i,minval,maxval,minrange,minel,maxel,flag,minind;

  //initializing to 0 index;
  for(i = 0;i <= k;i++) 
    ptr[i] = 0;

  minrange = INT_MAX;

  while(1)       
  {
      // for mainting the index of list containing the minimum element
      minind = -1; 
      minval = INT_MAX;
      maxval = INT_MIN;
      flag = 0;

      //iterating over all the list
      for(i = 0;i < k;i++)   
      {    
          // if every element of list[i] is traversed then break the loop
          if(ptr[i] == n)   
          {
            flag = 1;
            break;
          }
          // find minimum value among all the list elements pointing by the ptr[] array 
          if(ptr[i] < n && arr[i][ptr[i]] < minval)  
          {
              minind=i;  // update the index of the list
              minval=arr[i][ptr[i]];
          }
          // find maximum value among all the list elements pointing by the ptr[] array
          if(ptr[i] < n && arr[i][ptr[i]] > maxval)    
          {
              maxval = arr[i][ptr[i]];
          }
      }

      //if any list exhaust we will not get any better answer ,so break the while loop
      if(flag) 
        break;

      ptr[minind]++;

      //updating the minrange
      if((maxval-minval) < minrange)  
      {
          minel = minval;
          maxel = maxval;
          minrange = maxel - minel;
      }
  }

  printf("The smallest range is [%d , %d]\n",minel,maxel);
}  

Answer 1

免责声明:这实际上证明了 O(n * k^2) 的复杂性 - 我(还)没有删除它，因为也许有人会发现其中的缺陷我的推理，或者这才是真正的复杂性......

正如您已经注意到的那样，内部循环是 O(k)，问题是外部循环将执行多少次？

1. 一旦 ptr 中的值之一为 n，外层循环将停止执行。
2. 您从 ptr[i] = 0 开始，i = 1 .. k，并且对于外循环的每次执行，您递增 一个ptr 中的值。

最坏的情况是 ptr 中的所有值都连续递增，即当你得到:

ptr = 0 0 0 ... 0
ptr = 1 0 0 ... 0
ptr = 1 1 0 ... 0
...
ptr = 1 1 1 ... 1
ptr = 2 1 1 ... 1

在这种情况下，循环将在以下迭代处停止:

ptr = n (n-1) (n-1) ... (n-1)

从 0 0 0 ... 0 到 n (n-1) (n-1) ... (n-1) 需要多少时间？ O(n * k) 因为一个单元格从 1 到 n 需要 O(n) ，并且您在 ptr 中有 k 个单元格。

所以总复杂度似乎是O(n * k^2)，而不是O(n^2 * k)...