リスト操作が最も効率的です。

Question

リストの内容に対して2つの操作を実行する必要があります。リストには、エッジの重みと、これらのエッジがグラフに表示される重みが保持されます。

私のやりたいことは、リストを再整理することなく、リスト内の各x値に対して、リスト内の残りの値の合計がxより大きいことを確認してください。そうでない場合は、xをリストから削除する必要があります。

例えば私のリストを仮定は、数字3 31 10 100 3 5

（3 + 4 + 5 + 23 + 3 + 31 + 10 + 5）が100未満であるため、3 4 5 23、100意志が含まれていリストから削除する必要があります。

はこれまでのところ、私が思い付くことができた私は、より効率的な方法でこれを実現するにはどうすればよい

static double calculatesum(List<Edge> e) 
     { 
      double total = e.Sum(item => item.segmentlength); 
      //what I want to check each and then delete when I hit one I need to deactivate 
      foreach (Edge edge in e) 
      { 
       if (1 > (total - edge.segmentlength)) 
       { 
        edge.isactive = false; 
        total -= edge.segmentlength; 
       } 
      } 

      return 0; 
     } 

のですか？

Answer 1

これは、あなたが最も効果的であることを意味します。

あなたが最も漸近的な複雑さを探しているなら、ソートを行います（そして各要素の場所を覚えておいてください）。リストに単純な数字があるため、重量が制限されていると、おそらくO(n*log n)よりもうまくいくかもしれません。次に、単に合計を計算し、最後の要素を引き算して合計と比較し、必要に応じて終了するまで削除します。

削除する要素が2つしかない場合は、合計内の最大要素を検索し、削除する要素がなくなるまでこの手順を繰り返します。それO（n）は次のようにしますようにするに

Answer 2

：それはO（n）の

だろうここまで

1. create sum of all elements 
2. for each element 
2a. substract element from sum 
2b. check new sum against element 
2ba if to remove remember element 
2bb else add element to sum 
3. remove remembered elements 

私は、どの要素がもう削除されなくなるまで、このの複数の実行を検討することを忘れていました。したがって、最悪の場合は、未解散の場合はO（n^2）であり、事前解雇の場合はO（n + n log n）である。