時間從每個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) ...