アルゴリズムのパフォーマンスを研究していたときに、Googleの模擬インタビューからこのビデオに出会いました。 大規模なテクノロジー企業でインタビューがどのように行われるかについてのアイデアを提供するだけでなく、アルゴリズムの問題がどのように解決されるかを最も効率的に理解することもできます。
この記事は、ビデオの一種です。 その中で、示されているすべてのソリューションに加えて、JavaScriptでの自分のバージョンのソリューションについてコメントします。 各アルゴリズムのニュアンスについても説明します。
「Habr」の読者には、「Habr」プロモーションコードを使用してSkillboxコースに登録すると10,000ルーブルの割引があります。
Skillboxの推奨事項：実践コース「Mobile Developer PRO」 。
問題の声明
順序付けられた配列と特定の値が与えられます。 次に、配列の2つの数値の合計が指定された値と等しくなるかどうかに応じて、trueまたはfalseを返す関数を作成するように求められます。
言い換えると、配列に2つの整数xとyがあり、それらが追加されたときに、指定された値と等しいですか？
例A
配列[1、2、4、9]と値8が与えられた場合、関数はfalseを返します。配列の2つの数値が合計で8を与えることはできないためです。
例B
ただし、配列[1、2、4、4]で値が8の場合、4 + 4 = 8であるため、関数はtrueを返します。
ソリューション1. Bruteforce
時間的難易度：O（N²）。
空間的な複雑さ：O（1）。
最も明白な意味は、ネストされたループのペアを使用することです。
const findSum = (arr, val) => { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { if (i !== j && arr[i] + arr[j] === val) { return true; }; }; }; return false; };
このソリューションは、配列内の2つの要素のすべての可能な合計をチェックし、インデックスの各ペアを2回比較するため、効果的とは言えません。 （たとえば、i = 1およびj = 2の場合-これは実際にはi = 2およびj = 1と比較することと同じですが、このソリューションでは両方のオプションを試します）。
このソリューションでは、ネストされたforループのペアを使用しているため、時間の複雑さはO（N²）の2次関数です。
解決策2.バイナリ（バイナリ）検索
時間的な難易度：O（Nlog（N））。
空間的な複雑さ：O（1） 。
配列は順序付けられているため、バイナリ検索を使用してソリューションを検索できます。 これは、順序配列の最も効率的なアルゴリズムです。 バイナリ検索自体にはO（ログ（N））ランタイムがあります。 ただし、forループを使用して、各要素を他のすべての値と照合する必要があります。
ソリューションは次のようになります。 すべてを明確にするために、別の関数を使用してバイナリ検索を制御します。 removeIndex（）関数と同様に、配列のバージョンから指定されたインデックスを引いたものを返します。
const findSum = (arr, val) => { for (let i = 0; i < arr.length; i++){ if (binarySearch(removeIndex(arr, i), val - arr[i])) { return true; } }; return false; }; const removeIndex = (arr, i) => { return arr.slice(0, i).concat(arr.slice(i + 1, arr.length)); }; const binarySearch = (arr, val) => { let start = 0; let end = arr.length - 1; let pivot = Math.floor(arr.length / 2); while (start < end) { if (val < arr[pivot]) { end = pivot - 1; } else if (val > arr[pivot]) { start = pivot + 1; }; pivot = Math.floor((start + end) / 2); if (arr[pivot] === val) { return true; } }; return false; };
アルゴリズムはインデックス[0]から始まります。 次に、最初のインデックスを除く配列のバージョンを作成し、バイナリ検索を使用して、残りの値を配列に追加して必要な量を取得できるかどうかを確認します。 このアクションは、配列内の要素ごとに1回実行されます。
forループ自体はO（N）の線形時間複雑度を持ちますが、forループ内でバイナリ検索を実行し、O（Nlog（N））の合計時間複雑度を与えます。 このソリューションは以前のものよりも優れていますが、まだ改善すべきことがあります。
解決策3.線形時間
時間的難易度：O（N）。
空間的な複雑さ：O（1）。
ここで、配列がソートされていることを覚えて、問題を解決します。 解決策は、最初と最後に1つずつの2つの数字を使用することです。 結果が必要な結果と異なる場合、開始点と終了点を変更します。
最後に、目的の値を満たしてtrueを返すか、開始点と終了点が収束してfalseを返します。
const findSum = (arr, val) => { let start = 0; let end = arr.length - 1; while (start < end) { let sum = arr[start] + arr[end]; if (sum > val) { end -= 1; } else if (sum < val) { start += 1; } else { return true; }; }; return false; };
これですべてが正常になり、解決策が最適なようです。 しかし、配列が注文されたことを誰が保証しますか？
それで何？
一見、最初に配列を並べ替えてから、上記のソリューションを使用できます。 しかし、これはランタイムにどのように影響しますか？
最適なアルゴリズムは、時間計算量O（Nlog（N））の高速ソートです。 最適なソリューションで使用すると、パフォーマンスがO（N）からO（Nlog（N））に変わります。 順序付けられていない配列で線形解を見つけることは可能ですか？
決定4
時間的難易度：O（N）。
空間的な複雑さ：O（N）。
はい、線形解が存在します。このため、探している一致のリストを含む新しい配列を作成する必要があります。 ここでのトレードオフは、メモリをより積極的に使用することです。これは、O（1）を超える空間的複雑さを持つ記事の唯一のソリューションです。
この配列の最初の値が1で、検索値が8の場合、「検索値」の配列に値7を追加できます。
次に、配列の各要素を処理して、「検索値」の配列をチェックし、そのうちの1つが値と等しいかどうかを確認できます。 はいの場合、trueを返します。
const findSum = (arr, val) => { let searchValues = [val - arr[0]]; for (let i = 1; i < arr.length; i++) { let searchVal = val - arr[i]; if (searchValues.includes(arr[i])) { return true; } else { searchValues.push(searchVal); } }; return false; };
ソリューションの基本はforループです。これは、上で見たように、O（N）の線形時間計算量を持ちます。
関数の2番目の反復部分はArray.prototype.include（）です。これは、配列に指定された値が含まれているかどうかに応じてtrueまたはfalseを返すJavaScriptメソッドです。
Array.prototype.includes（）の時間の複雑さを調べるには、MDNによって提供される（JavaScriptで記述された）ポリフィルを調べるか、Google V8（C ++）などのJavaScriptエンジンのソースコードのメソッドを使用します。
// https://tc39.github.io/ecma262/#sec-array.prototype.includes if (!Array.prototype.includes) { Object.defineProperty(Array.prototype, 'includes', { value: function(valueToFind, fromIndex) { if (this == null) { throw new TypeError('"this" is null or not defined'); } // 1. Let O be ? ToObject(this value). var o = Object(this); // 2. Let len be ? ToLength(? Get(O, "length")). var len = o.length >>> 0; // 3. If len is 0, return false. if (len === 0) { return false; } // 4. Let n be ? ToInteger(fromIndex). // (If fromIndex is undefined, this step produces the value 0.) var n = fromIndex | 0; // 5. If n ≥ 0, then // a. Let k be n. // 6. Else n < 0, // a. Let k be len + n. // b. If k < 0, let k be 0. var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0); function sameValueZero(x, y) { return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y)); } // 7. Repeat, while k < len while (k < len) { // a. Let elementK be the result of ? Get(O, ! ToString(k)). // b. If SameValueZero(valueToFind, elementK) is true, return true. if (sameValueZero(o[k], valueToFind)) { return true; } // c. Increase k by 1. k++; } // 8. Return false return false; } }); }
ここで、Array.prototype.include（）の反復部分は、ステップ7のwhileループであり、指定された配列の全長を（ほぼ）横断します。 これは、その時間的な複雑さも線形であることを意味します。 さて、これは常にメイン配列の1ステップ後ろにあるため、時間の複雑さはO（N +（N-1））です。 Big O Notationを使用して、O（N）に簡略化します。入力サイズが大きくなるとNが最大の影響を与えるためです。
空間的複雑度に関しては、追加の配列が必要であり、その長さは元の配列を反映し（マイナス1、はい、これは無視できます）、O（N）の空間的複雑度につながります。 まあ、メモリ使用量を増やすと、アルゴリズムの効率が最大になります。
この記事がビデオインタビューの添付ファイルとして役立つことを願っています。 単純な問題は、使用されるリソースの量（時間、メモリ）が異なる複数の異なる方法で解決できることを示しています。
Skillboxの推奨事項：
- 応用Python Data Analystオンラインコース。
- オンラインコース「Profession frontend-developer」 。
- 実用的な年次コース「PHP開発者0からPRO」 。