O(n2) 以外に解決策はありますか。すべての値をループして合計を取得することを考えていました
2 に答える
8
2 つの最大の要素から作られるペアは、合計が最大になります。2つの最大の要素を見つけて合計するだけです-それはですO(n)
k合計が最大数になる一般的な要素の場合、選択アルゴリズムを使用して k 個の最大要素を見つけ、次に 2 回目の繰り返しで、それより大きいすべての要素を合計します。
于 2012-04-27T12:27:39.307 に答える
3
2 つの最大数を取得したい場合、必要なループは 1 つだけです。これにより、アルゴリズムは になりO(n)ませんO(n^2)。
より複雑なペア分析が必要な場合は、整数に対してクイックソートを実行しますO(n log n)。次に、最大のペアとなる 2 つの最大の数値と、必要なその他のペアの組み合わせを選択できます。
于 2012-04-27T12:27:43.037 に答える