殺されたプロセスの数をカウントする

Question

コンピュータには合計n個のプロセスがあり、xで示される新しいプロセスはキューで待機しています。 私たちはまた、すべてのn個のプロセスのメモリを与えました。 これで、新しいプロセスによって置き換えられるプロセスの最小数を見つけることができます。 と仮定してn = 5 （新しいプロセスのメモリサイズ）x = 9 とメモリが5つのプロセスすべてを占有= 2 1 3 4 5 ここで4と5を削除すると最小カウントは2（4 + 5 = 9 ）。 私はこれをo（n^2）で試しましたが、私はソリューションを最適化したいです。 をお勧めします。私たちが最初に私たちに与えられたプロセスのリストを操作することが許可されている場合

Answer 1

さて、あなたは、単に大きさの降順でのプロセスのリストを並べ替えることができます。そして、問題は、リスト全体を反復して、遭遇する各プロセスのメモリ割り当てを合計するだけです。 xを超えると（新しいプロセスに必要な割り当て）、現在のインデックス+ 1が返されます。これはこれまでに遭遇した（そして終了した）プロセスの数です。

以下は、それを実装するサンプルのPythonコードです。

def solve(processes, x): 
    processes.sort(reverse=True) 
    sum_of_freed_memory = 0 
    for i in range(len(processes)): 
     sum_of_freed_memory += processes[i] 
     if sum_of_freed_memory >= x: 
      return (i+1) 
    return -1 # to not crash if/when total memory is smaller than x 

あなたが望む出力を生成し、作業hereでこのコードを観察することができます。

入力として与えられた元のリストを操作できなかったとしても、私たちの解でO（n）スペースを使用することが許されていれば、初期リストをコピーして同じコピーを使用することができます。コードに関して、関数solve（）の最初の行を以下の行に置き換えると、それが実行されます。

processes = sorted(processes, reverse=True) 

このコードで取るアプローチは貪欲です。各ステップで、次のような理由が考えられます。私はもう1つのプロセスを終了してから、まだ実行中のプロセスの中でを最大のメモリを使用するものを強制終了して、十分なメモリを割り当てる可能性が最も高くなります可能なのはです。言い換えると、もう1つのプロセスを強制終了して十分な領域を確保する方法があれば、最大のメモリを使用してプロセスを終了しますが、他のプロセスを終了するには不十分です。その正式な証拠ではありませんが、私はこの推論がアルゴリズムがなぜ機能するのかを説明していると思います。

ソーティングの複雑さは、O（NlogN）あり、トラバーサルはO（N）あります。従って、アルゴリズムの全体的な複雑さは、O（NlogN）となる。