2つのforループでは、inner forループが1000回増加しますが、速度は100倍に増加するだけですか？

Question

私はアルゴリズムの計算の複雑さを分析する過程にありますが、私は2つのforループを持っています。

short i=0; 
    short j=0; 
    short ii=0; 
    short[] counts = new short[2]; 

    int label_size = MapRedUtils.label_size; 
    int max_index=0;       
    int sample_size =data.getSampleSize(); 

    float max_ig = 0; 
    float totalVar=0; 
    float var=0; 
    float cov_ig; 

    float[] tocopy = new float[label_size];   
    float[][] sums = new float[2][]; 
    float[] totalSum = new float[label_size]; 



    byte value; 
    ByteBuffer label = ByteBuffer.allocate(label_size*4); 

    for(j=0; j<2; j++)   
     sums[j] = new float[label_size]; 

    for(ii=0; ii<3; ii++)// 3 ways of split the current node 
    {   
      long startTime; 
    long endTime; 
    long totalTime; 
    startTime = System.currentTimeMillis(); 
     counts[0]=0; 
     counts[1]=0; 

     System.arraycopy(tocopy,0,totalSum,0,label_size); 
     System.arraycopy(tocopy,0,sums[0],0,label_size); 
     System.arraycopy(tocopy,0,sums[1],0,label_size); 

     for (i = 0; i < sample_size; i++) 
     { 
      OneSample instance = data.get(i); 
      value = (byte) instance.getTheGenoytpe(snpid); 

      label = instance.getPhenotype();                   

      if(value==ii) 
      { 
       counts[0]++; 
       for(j=0; j< label_size; j++) 
        sums[0][j] += label.getFloat(j*4); 
      } 
      else 
      { 
       counts[1]++;      
       for(j=0; j< label_size; j++) 
        sums[1][j] += label.getFloat(j*4);      
      } 

      for(j=0; j< label_size; j++) 
       totalSum[j] += label.getFloat(j*4); 
     }            

      totalVar=0; 
      var=0; 
     for(i=0; i< label_size; i++) 
     { 
      totalVar += totalSum[i]*totalSum[i];   
     } 

     totalVar = totalVar/sample_size;//it is averaged by sample size 

     for(j=0; j< 2; j++) 
      //var += sumSquared(sums[j], MapRedUtils.inverse_covariance , counts[j]); 
      var += sumSquared(sums[j], counts[j]); 


     cov_ig = var- totalVar; 

     if(cov_ig > max_ig) 
     { 
      max_ig=cov_ig; 
      max_index=ii; 
     } 
     endTime = System.currentTimeMillis();      
     totalTime = (endTime - startTime); 
     System.out.println(totalTime); 

私はlabel_size = 1とlabel_size = 1000からインナーlabel_sizeを増やし、私は別の実行のための唯一の40-100倍実際に実行時間が増加しながら、実行している時間は、1000倍に増やす必要があります期待しています。 これはなぜですか？

Answer 1

ラベルが1の場合、外側のループのほとんどの時間は「ここで何か」で取り込まれ、内側のループを設定します。作品。ここで何かをすると仮定し、内部ループの設定には100単位の時間がかかり、「ここで何かする」にはわずか10単位しかかかりません。プログラムの合計実行時間は110 * sample_sizeです。今度はラベルを1000に増やします。100 + 10 * 1000 = 10100です。したがって、合計実行時間は10100 * sample_sizeです。 10100/110 = 91.8。 「ここに何かする」には時間がかかったため、ラベルの増加による影響が大幅に軽減されました。古いラベルの値と新しいラベルの値の比だけでなく、「ここに何かする」と「ここで何かする」の比率を考慮する必要があります。