JavaScript でアルゴリズムの複雑さを学ぶ

この記事では、アルゴリズムの文脈における「二次」や「n log(n)」などの用語の意味について説明します。

[[314140]]

次の例では、5 つの要素を含む配列と 50 の要素を含む配列の 2 つを参照します。また、JavaScript の便利なパフォーマンス API を使用して、実行時間の違いを測定します。

定数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];

Big O 表記法とは何ですか?

Big O 表記法は、データ セットのサイズが大きくなるにつれて計算タスクの難易度が全体的に増加することを表現する方法です。他にも表記法はありますが、最悪のシナリオに焦点を当てているため、定量化や検討が容易なビッグ O 表記法が一般的に最もよく使用されます。最悪のシナリオとは、タスクを完了するために最も多くの操作を必要とするシナリオを意味します。1 秒以内にキューブを解くことができたとしても、一度だけひねっただけでは最善の成果とは言えません。

これは、アルゴリズムをさらに深く理解するにつれて非常に役立ちます。コードを書くときにこの関係を理解し​​、どこに費やされているかがわかるからです。

Big O 表記法について詳しく学ぶと、次の図のさまざまなバリエーションがわかるようになります。複雑さはできるだけ低く抑え、できれば O(n) を超えないようにします。

オー(1)

これは理想的な状況であり、プロジェクトの数が 1 つであろうと 100 万であろうと、完了するまでの時間は同じままです。単一の操作を実行するほとんどの操作は O(1) です。配列へのデータの書き込み、特定のインデックスでの項目の取得、子要素の追加などは、配列の長さに関係なく、すべて同じ時間がかかります。

定数 a1 = パフォーマンス.now();
 smArr.push(27);
定数 a2 = パフォーマンス.now();
 console.log(` Time : ${a2 - a1}`); // 1ミリ秒未満
 
 
 b1 はパフォーマンスを今維持します。
 bigArr.push(27);
定数 b2 = パフォーマンス.now();
 console.log(` Time : ${b2 - b1}`); // 1ミリ秒未満

の上）

デフォルトでは、データのサイズと完了までの時間の間には 1 対 1 の関係があるため、すべてのループは線形に増加します。したがって、配列項目が 1,000 個ある場合は、1,000 倍の時間がかかります。

定数 a1 = パフォーマンス.now();
 smArr.forEach(item => console.log(item));
定数 a2 = パフォーマンス.now();
 console.log(` Time : ${a2 - a1}`); // 3ミリ秒
 
 b1 はパフォーマンスを今維持します。
 bigArr.forEach(item => console.log(item));
定数 b2 = パフォーマンス.now();
 console.log(` Time : ${b2 - b1}`); // 13ミリ秒

（n^2）

指数関数的成長は私たち全員が陥る罠です。配列内のすべての項目に一致するペアを見つける必要がありますか? ループ内にループを配置すると、1,000 項目の配列を 100 万回の操作検索に変換して、ブラウザーが応答しなくなる可能性があります。二重にネストされたループを使用して 100 万回の操作を実行するよりも、2 つの別々のループで 2,000 回の操作を実行する方が適切です。

定数 a1 = パフォーマンス.now();
 smArr.forEach(() => {
    arr2.forEach(item => console.log(item));
 });
定数 a2 = パフォーマンス.now();
 console.log(` Time : ${a2 - a1}`); // 8ミリ秒
 
 
 b1 はパフォーマンスを今維持します。
 bigArr.forEach(() => {
    arr2.forEach(item => console.log(item));
 });
定数 b2 = パフォーマンス.now();
 console.log(` Time : ${b2 - b1}`); // 307 ミリ秒

O(logn) です

対数的増加の良い比喩としては、「記法」のような単語を辞書で調べることを想像することだと思います。用語ごとに検索するのではなく、最初に「N」セクションを見つけ、次に「OPQ」ページを見つけて、一致するものが見つかるまでアルファベット順にリストを検索します。

この「分割統治」アプローチでは、何かを見つけるのにかかる時間は辞書のサイズによって異なりますが、O(n) にはほど遠いです。データの大部分を参照せずに段階的に具体的な部分を検索するため、1,000 個のアイテムを検索する場合は 10 回未満の操作で済み、100 万個のアイテムを検索する場合は 20 回未満の操作で済み、効率が最大限に高まります。

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

定数ソート = arr => {
  (arr.length < 2) の場合はarrを返します。 
 
  ピボットをarr[0]とします。
  左を[]とします。
  右に[] とします。 
 
 ( i = 1、total = arr.length、i < total、i++ とします) {
    もしarr[i] < pivot ならば、 arr[i]を左にプッシュします。
それ以外 右に.push(arr[i]);
  };
戻る[
    ...ソート(左)、
    ピボット、
    ...並べ替え(右)
  ];
 };
 sort(smArr); // 0 ミリ秒
sort(bigArr); // 1ミリ秒

の上！）

最悪の可能性は階乗成長です。典型的な例は巡回セールスマン問題です。距離がそれぞれ異なる都市がたくさんある場合、すべての都市から出発点に戻る最短ルートをどのように見つけるのでしょうか。力ずくのアプローチは、各都市間のすべての可能なルート距離をチェックすることですが、これは階乗であり、すぐに手に負えなくなります。

この問題はすぐに非常に複雑になる可能性があるため、短い再帰関数を使用してこの複雑さを示します。この関数は、ある数値をその数値自身で乗算し、その数値から 1 を引きます。階乗の各数値は 0 に達するまでこのように計算され、各再帰層ではその積が元の数値に加算されます。

階乗は、単に 1 から始まってその数まで増加する積です。すると、6! は 1x2x3x4x5x6 = 720 になります。

定数階乗 = n => {
  num = n とします。 
 
  (n === 0)の場合は1を返す
( i = 0; i < n; i++ とします) {
    num = n * 階乗(n - 1);
  }; 
 
数値を返します。
 };
階乗(1); // 2ミリ秒
階乗(5); // 3ミリ秒
階乗(10); // 85ミリ秒
階乗(12); // 11,942ミリ秒

当初は階乗(15)を表示するつもりでしたが、12を超える値は多すぎてページがクラッシュするため、これを避ける必要があることがわかります。

結論

パフォーマンスの高いコードを書く必要があるというのは議論の余地のない事実のように思えますが、ほぼすべての開発者が「とにかく機能するから」という理由で、少なくとも二重、あるいは三重にネストされたループを作成したことがあると思います。 Big O 表記法は、これまでにない方法で複雑さを表現し、考えるために不可欠です。