アルゴリズムのパフォーマンスを研究していたときに、これを見つけました 。 これにより、大手テクノロジー企業で面接がどのように行われるかがわかるだけでなく、アルゴリズムの問題がどのようにしてできるだけ効率的に解決されるのかを理解することもできます。
この記事はビデオの付随的なものです。 その中で、表示されているすべてのソリューションに関するコメントに加えて、JavaScript で作成した独自のバージョンのソリューションについても説明します。 各アルゴリズムの微妙な違いについても説明します。
リマインダー： 「Habr」のすべての読者が対象 - 「Habr」プロモーション コードを使用してスキルボックス コースに登録すると 10 ルーブルの割引。
スキルボックスは次のことを推奨します。 実践コース .
問題の定式化
順序付けられた配列と特定の値が与えられます。 次に、配列内の XNUMX つの数値の合計が指定された値と等しくなるかどうかに応じて true または false を返す関数を作成するように求められます。
言い換えると、配列内に XNUMX つの整数 x と y があり、それらを合計すると指定された値と等しくなりますか?
例A
配列 [1, 2, 4, 9] が与えられ、その値が 8 の場合、配列内の 8 つの数値の合計が XNUMX になることはないため、関数は false を返します。
例B
ただし、それが配列 [1, 2, 4, 4] で、値が 8 の場合、4 + 4 = 8 であるため、関数は true を返す必要があります。
解決策 1: ブルートフォース
時間計算量: 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;
};このソリューションは、配列内の 1 つの要素の可能な合計をすべてチェックし、インデックスのすべてのペアを 2 回比較するため、効率的ではありません。 (たとえば、i = 2 および j = 1 の場合は、実際には i = XNUMX および j = XNUMX と比較するのと同じですが、この解決策では両方のオプションを試します)。
このソリューションではネストされた for ループのペアを使用するため、時間計算量は O(N²) の二次関数になります。
解決策 2: 二分探索
時間計算量: O(Nlog(N))。
空間の複雑さ: O(1).
配列は順序付けされているため、二分探索を使用して解を検索できます。 これは、順序付けされた配列にとって最も効率的なアルゴリズムです。 二分探索自体の実行時間は O(log(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] から始まります。 次に、最初のインデックスを除いたバージョンの配列を作成し、二分探索を使用して、残りの値を配列に追加して目的の合計を生成できるかどうかを確認します。 このアクションは、配列内の要素ごとに XNUMX 回実行されます。
for ループ自体の線形時間計算量は O(N) ですが、for ループ内では二分探索が実行され、全体の時間計算量は O(Nlog(N)) になります。 このソリューションは以前のソリューションよりも優れていますが、まだ改善の余地があります。
解決策 3: 線形時間
時間計算量: O(N)。
空間複雑度: O(1)。
ここで、配列がソートされていることを思い出しながら、問題を解決していきます。 解決策は、先頭と末尾に XNUMX つずつ、計 XNUMX つの数字を取ることです。 結果が必要な結果と異なる場合は、開始点と終了点を変更します。
最終的には、目的の値が得られて 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 を「検索値」配列に追加できます。
次に、配列の各要素を処理するときに、「検索値」の配列をチェックし、それらの XNUMX つが値と等しいかどうかを確認できます。 「はい」の場合は、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) です。
関数の XNUMX 番目の反復部分は 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 - XNUMX)) です。 Big O Notation を使用して、O(N) に単純化します。入力サイズを増やすときに最も大きな影響を与えるのは N であるためです。
空間的複雑さに関しては、元の配列を反映する長さの追加の配列が必要です (マイナス XNUMX ですが、無視できます)。その結果、空間的複雑さは O(N) になります。 メモリ使用量が増加すると、アルゴリズムの効率が最大化されます。
この記事がビデオインタビューの補足として役立つことを願っています。 これは、使用されるリソース (時間、メモリ) の量が異なるいくつかの異なる方法で、単純な問題を解決できることを示しています。
スキルボックスは次のことを推奨します。
- オンラインコースの申し込み .
- オンラインコース .
- 実践一年コース .
出所： habr.com