時間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. i = 1 .. kの場合はptr[i] = 0で始まり、外側ループの実行ごとにの場合はを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までは1つのセルにO(n)が必要で、ptrにはkのセルがあるためです。

だから総複雑さがO(n * k^2)のようだ、とないO(n^2 * k) ...