时间从每个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)，因为它需要O(n)一个单元格从1到n，并且您在ptr中有k单元格。

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