DSA Big O
1.0.0
これらのドリルでは、アルゴリズムの大きな複雑さを決定する練習を練習します。ドリルごとに、機能を備えたコードスニペットに提供すると、コードを実行せずに分析することで、大きなOの複雑さを解決します。
次のアルゴリズムの大きなOを決定します。15人の部屋に座っています。あなたはあなたの犬のために、できれば同じ品種のプレイメイトを見つけたいです。ですから、15人のうち誰かがあなたの犬と同じ品種を持っているかどうかを知りたいです。あなたは立ち上がって叫びます。ここにはゴールデンレトリバーがあり、私のゴールデンのプレイデートになりたいと思っています。誰かが叫ぶ - 「私は彼を連れてきて喜んでいる」
次のアルゴリズムの大きなOを決定します。15人の部屋に座っています。あなたは同じ品種の犬のためにプレイメイトを見つけたいです。ですから、15人のうち誰かがあなたの犬と同じ品種を持っているかどうかを知りたいです。あなたは最初の人から始めて、彼がゴールデンレトリバーを持っているかどうか彼に尋ねます。彼はノーと言います、そしてあなたは次の人に、そして次の人に尋ね、次はあなたが金色の人や他に尋ねる人がいない人を見つけるまで尋ねます。
次のアルゴリズムの大きなOは何ですか？あなたの答えを説明してください
if (value % 2 === 0) {
return true;
}
else {
return false;
}
}
次のアルゴリズムの大きなOは何ですか？あなたの答えを説明してください
for (let i = 0; i < arr1.length; i++) {
const el1 = arr1[i];
for (let j = 0; j < arr2.length; j++) {
const el2 = arr2[j];
if (el1 === el2) return true;
}
}
return false;
}
次のアルゴリズムの大きなOは何ですか？あなたの答えを説明してください
for (let i = 0; i < array.length; i++) {
array[i] *= 2;
}
return array;
}
次のアルゴリズムの大きなOは何ですか？あなたの答えを説明してください
for (let i = 0; i < array.length; i++) {
if (array[i] === item) {
return i;
}
}
}
次のアルゴリズムの大きなOは何ですか？あなたの答えを説明してください
for (let i = 0; i < arr.length; i++) {
for(let j = i + 1; j < arr.length; j++) {
console.log(arr[i] + ", " + arr[j] );
}
}
}
次のアルゴリズムは何をしますか？ランタイムの複雑さは何ですか？あなたの答えを説明してください
let result = [];
for (let i = 1; i <= num; i++) {
if (i === 1) {
result.push(0);
}
else if (i === 2) {
result.push(1);
}
else {
result.push(result[i - 2] + result[i - 3]);
}
}
return result;
}
この例では、上記の素朴な検索よりも洗練されたアプローチを使用して検索する問題に戻ります。入力配列が常にソートされていると仮定します。次のアルゴリズムの大きなOは何ですか？あなたの答えを説明してください
let minIndex = 0;
let maxIndex = array.length - 1;
let currentIndex;
let currentElement;
while (minIndex <= maxIndex) {
currentIndex = Math.floor((minIndex + maxIndex) / 2);
currentElement = array[currentIndex];
if (currentElement < item) {
minIndex = currentIndex + 1;
}
else if (currentElement > item) {
maxIndex = currentIndex - 1;
}
else {
return currentIndex;
}
}
return -1;
}
次のアルゴリズムの大きなOは何ですか？あなたの答えを説明してください
return arr[Math.floor(Math.random() * arr.length)];
}
次のアルゴリズムは何をしますか？次のアルゴリズムの大きなOは何ですか？あなたの答えを説明してください
if (n < 2 || n % 1 !== 0) {
return false;
}
for (let i = 2; i < n; ++i) {
if (n % i === 0) return false;
}
return true;
}
ハノイの塔は非常に有名な数学的なパズルです（一部のゲームと呼んでいます！）。これがどのように進むかです：
3つのロッドと、あらゆるロッドにスライドできるさまざまなサイズのディスクがあります。パズルは、ディスクが1つのロッドにサイズの昇順できちんと積み重ねられ、上部の最小のディスク（円錐形の形を作る）から始まります。他の2つのロッドはそもそも空です。
パズルの目標は、ロッドのスタック全体を別のロッドに移動することです（以前に積み重ねられた元のロッドではありません）。これは、次のルールに従う必要があります。
あなたの仕事：
再帰的ではなく、12回繰り返しJSファイルを解きます。
このリポジトリからソリューションを取り、それぞれの時間の複雑さ（大きなo）を特定します。
JSファイル12の反復運動ドリルからソリューションを受け取り、それぞれの時間の複雑さ（大きなO）を特定します。
