JavaScriptを介したBigO表記の理解

投稿日: 2022-04-20 2022-10-06
タグ: javascript

開発者としての就職を検討したことがあるなら、おそらくこの Googleの面接に出くわし、「彼らは一体何を話しているのか」と疑問に思ったことがあるでしょう。この記事では、「二次」や「nlogn」などの用語を使用することの意味を探ります。

これらの例のいくつかでは、これら2つの配列を参照します。1つは5つのアイテムで、もう1つは50のアイテムです。また、JavaScriptの便利なパフォーマンスAPI を使用して、実行時間の違いを測定します。

const smArr = [5, 3, 2, 35, 2];

const bigArr = [5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2];

Big O表記とは何ですか？

Big O表記は、データセットを増やすにつれてタスクの計算の難しさが一般的に増加することを表す方法にすぎません。他の表記法もありますが、O表記法は、定量化と検討が容易な最悪のシナリオに焦点を当てているため、一般的に最もよく使用されます。最悪の場合、タスクを完了するためにほとんどの操作が必要になることを意味します。ルービックキューブを1秒で解くと、1ターンしかかからなかったとしても、自分が最高だとは言えません。

アルゴリズムについて詳しく知ると、これらの式が頻繁に使用されることがわかります。この関係を理解しながらコードを記述することは、操作がほぼ瞬時に行われるか、数分かかることと、Firebaseなどの外部プロセッサで莫大な金額を浪費することの違いになる可能性があるためです。。

Big O表記についてさらに学習すると、このグラフのさまざまな、より優れたバリエーションが表示される可能性があります。複雑さをできるだけ低く、まっすぐに保ち、理想的にはO（n）を超えるものを避けたいと考えています。

O（1）

これは理想的であり、アイテムがいくつあっても、100万であろうと100万であろうと、完了するまでの時間は同じままです。単一の操作を実行するほとんどの操作はO（1）です。配列へのプッシュ、特定のインデックスでのアイテムの取得、子要素の追加などは、配列の長さに関係なく、すべて同じ時間がかかります。

const a1 = performance.now();
smArr.push(27);
const a2 = performance.now();
console.log(`Time: ${a2 - a1}`); // Less than 1 Millisecond


const b1 = performance.now();
bigArr.push(27);
const b2 = performance.now();
console.log(`Time: ${b2 - b1}`); // Less than 1 Millisecond

の上）

デフォルトでは、データサイズと完了までの時間の間に1対1の関係があるため、すべてのループは線形成長の例です。したがって、アイテムが1,000倍多い配列は、正確に1,000倍長くかかります。

const a1 = performance.now();
smArr.forEach(item => console.log(item));
const a2 = performance.now();
console.log(`Time: ${a2 - a1}`); // 3 Milliseconds

const b1 = performance.now();
bigArr.forEach(item => console.log(item));
const b2 = performance.now();
console.log(`Time: ${b2 - b1}`); // 13 Milliseconds

O（n ^ 2）

指数関数的成長は、私たち全員が少なくとも一度は陥った罠です。配列内の各アイテムに一致するペアを見つける必要がありますか？ループをループ内に配置することは、1,000個のアイテムの配列を100万回の操作検索に変換し、ブラウザーをフリーズさせる優れた方法です。 2つのネストされたループで100万回実行するよりも、2回の別々のループで2,000回の操作を実行する方が常に適切です。

const a1 = performance.now();
smArr.forEach(() => {
    arr2.forEach(item => console.log(item));
});
const a2 = performance.now();
console.log(`Time: ${a2 - a1}`); // 8 Milliseconds


const b1 = performance.now();
bigArr.forEach(() => {
    arr2.forEach(item => console.log(item));
});
const b2 = performance.now();
console.log(`Time: ${b2 - b1}`); // 307 Milliseconds

O（log n）

対数関数的成長を理解するために私が聞いた最も良い例えは、辞書で「表記法」のような単語を検索することを想像することです。エントリを次々に検索することはできません。代わりに、「N」セクションを検索し、次に「OPQ」ページを検索して、一致するものが見つかるまでリストをアルファベット順に検索します。

この「分割統治」アプローチでは、何かを見つけるための時間は、辞書のサイズに応じて変化しますが、O（n）の割合にはほど遠いです。ほとんどのデータを確認せずに、より具体的なセクションを徐々に検索するため、1,000個のアイテムを検索すると、10回未満の操作で済み、100万個のアイテムでは20回未満の操作で済み、最大の効果が得られます。

この例では、単純なクイックソートを実行できます。

const sort = arr => {
  if (arr.length < 2) return arr;

  let pivot = arr[0];
  let left = [];
  let right = [];

  for (let i = 1, total = arr.length; i < total; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  };
  return [
    ...sort(left),
    pivot,
    ...sort(right)
  ];
};

sort(smArr); // 0 Milliseconds
sort(bigArr); // 1 Millisecond

の上！）

最後に、最悪の可能性の1つ、階乗の成長。この教科書の例は、旅行セールスマンの問題です。さまざまな距離の都市がたくさんある場合、それらすべての間を行き、出発点に戻る最短のルートをどのように見つけますか？力ずくの方法は、各都市間のすべての可能な構成間の距離をチェックすることです。これは階乗であり、すぐに手に負えなくなります。

その問題は非常にすぐに複雑になるため、短い再帰関数を使用してこの複雑さを示します。この関数は、それ自体から1を引いた独自の関数で数値を乗算します。階乗のすべての桁は、0に達するまで独自の関数を実行し、各再帰レイヤーはその積を元の数値に追加します。したがって、3に2を掛けて、関数を実行し、1を掛けて、関数を再度実行して0で停止し、6を返します。再帰はこのように非常に簡単に混乱します。

階乗は、その数までのすべての数の積にすぎません。だから6！ 1x2x3x4x5x6=720です。

const factorial = n => {
  let num = n;

  if (n === 0) return 1
  for (let i = 0; i < n; i++) {
    num = n * factorial(n - 1);
  };

  return num;
};

factorial(1); // 2 Milliseconds
factorial(5); // 3 Milliseconds
factorial(10); // 85 Milliseconds
factorial(12); //  11,942 Milliseconds

見せようと思った factorial(15) 代わりに、12を超えるものは多すぎてページがクラッシュしたため、これを回避する必要がある理由を正確に証明しました。

まとめ

コードのパフォーマンスを可能な限り維持することは明らかな懸念のように思われるかもしれませんが、ほとんどすべての開発者は、「正しく機能する」ため、少なくとも1回は2つまたは3つのネストされたループを作成していると確信しています。 Big O表記は、複雑さを表現するために非常に必要であり、複雑さについて考えることは、これまで不可能だった方法です。

getdocs

13036