-3
ジョブがあり、多くのワーカーが利用可能であると仮定します。 次のコードは、最適化の考え方が悪い可能性があります。 しかし複雑さを分析するためだけです。未知の確率の計算複雑度
A is a set of N worker
while (A is not empty)
{
B=empty set
foreach a1 in A
{
foreach a2 in A
{
b= merge(a1, a2)
if (b works better than a1 **and** b works better than a2)
add b to B
}
}
A=B
}
問題は、「bがa1とa2より優れている」という確率は不明です。 したがって、上記のコードの時間複雑さを見積もるにはどうすればよいですか？
あろう、 'B'は何ですか？ – fjardon
定数時間操作のように見えます。だからそれは問題ではない。 @Nico Schertler。 –
。問題を指摘してくれてありがとう。私はコードを修正し、Aはwhileループ内で更新されます。 merge（）は、a1とa2が結合されて1組のワーカーであることを示します。すなわち、「A」は当初、単一労働者のグループを含んでいた。それから、「A」は徐々に大きなグループを含む。 複雑さは 'if'ステートメントの数として数えられると仮定します。 –