1

2 つの合計の問題を解決するには、O(n) の複雑さのアルゴリズムを使用して実装できますが、私は O(n^2) の複雑さを試しました。これは、i 番目の整数の合計をそれぞれのターゲット値に対する残りの整数。以下は O(n^2) の実装です。2 つの実装では、numsは整数の配列、nは nums のサイズ、indexs はインデックスを保持するサイズ 2 の配列です。 2 つの整数の

for(int i=0; i<n; ++i)
for(int j=i+1; j<n; ++j) {
    if(nums[i] + nums[j] == target) {
        indices[0] = i; indices[1] = j; return indices;
    }
}

この実装は、140ms で問題を解決します。別の O(n^2) アプローチを試しました。これは、1 から n-1 までの各 k 値について、i 番目の整数と (i + k) 番目の整数の合計をターゲット値に対してチェックするというものです。実装は次のとおりです。

for(int k=1; k<n; k++)
for(i=0; i<n-k; i++) {
    int j=i+k;
    if(nums[i] + nums[j] == target) {
        indices[0] = i; indices[1] = j; return indices;
    }
}

ご覧のとおり、同じループ本体ですが、これははるかに高速に実行され、実行時間は 8 ミリ秒です。何故ですか？それは空間的局所性に関連していますか？

4

1 に答える 1

4

公正な比較では、両方のプログラムが最後まで実行され、それでもインデックスが見つかりません。見た目では、答えが存在するケースに対してテストしています。当然、その場合、答えを探す順序は非常に重要です。

たとえば、唯一の答えが の{n - 2, n - 1}場合、最初のコードではそれを見つけるのに O(n^2) 操作が必要ですが、2 番目のコードでは O(n) で見つけます。生成するコード:

std::fill (&num[0], &num[0] + n, 0);
target = 2;
num[n - 2] = 1;
num[n - 1] = 1;

逆に、唯一の答えが の{0, n - 1}場合、最初のコードは O(n) でそれを見つけますが、2 番目のコードは O(n^2) ステップを実行します。生成するコード:

std::fill (&num[0], &num[0] + n, 0);
target = 2;
num[0] = 1;
num[n - 1] = 1;

配列であろうとベクトルであろうと、それ&num[0]が機能することを保証することです。num

于 2019-12-02T11:44:22.987 に答える