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

概要

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

次の例では、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 ならば left.push(arr[i]);
    そうでなければ right.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 表記法は、これまでにない方法で複雑さを表現し、考えるために不可欠です。

上記は、JavaScript でアルゴリズムの複雑さを学習する方法の詳細です。JS アルゴリズムの複雑さの詳細については、123WORDPRESS.COM の他の関連記事に注目してください。