JavaScriptアルゴリズムの複雑度分析

新しい年は、まず簡単で重要な知識点を共有するために整理します.時間の複雑さと空間の複雑さ.前の文章の中で、時間の複雑さを言っていますから、まだ分からない仲間もいるかもしれません.(ps:前の記事にコメントしてくれた友達ががっかりしないでください.ゆっくり来てください.)
まずみんなに思考問題を出して、テーマ:sum=1+2+3++n、sumの値を計算します.
なぜ複雑度分析が必要ですか?

データ構造とアルゴリズムを学習すると、「速い」と「省」の問題を理解するために、つまりどのようにあなたのコードを設計すれば演算効率が速くなり、スペースが小さくなりますか?コードの実行効率はどう計算しますか?ここでは複雑度分析が使われます.

実行時間はコードで正確に計算できますが、多くの限界があります.

データ規模の違いは試験結果に直接影響を与えます.例えば、同じ並べ替えアルゴリズムでは、順序が違っています.最後の計算効率の結果も違っています.ちょうど配列が整いました.実行時間はもっと短くなります.また、例えばデータ規模が小さいと、テスト結果もアルゴリズムの性能に反応しないかもしれません.

試験の環境によっては試験結果にも影響があります.例えば同じコードをそれぞれi 3とi 7のプロセッサでテストすれば、i 7のテスト時間はi 3より短いはずです.

したがって、正確なテスト結果ではなく、コードの実行時間を推定する方法が必要です.これは複雑度分析です.
大O複雑度表示法
一例で開始します.以下のコードの実行時間を見積もってください.

function total(n) { // 1
      var sum = 0; // 2
      for (var i = 0; i < n; i++) { // 3
        sum += i; // 4
      } //5 
    } //6

各行のコードが実行される時間が同じであると仮定して、tを記入すると、上の関数の2行目にはtの時間が必要であり、3行目と4行目にはそれぞれn個のtの時間が必要である.このコードの総実行時間は(2 n＋1)＊tである.
上記の分析方法に従って、下記のコードの実行時間を見積もってください.

 function total(n) { // 1
      var sum = 0; // 2
      for (var i = 0; i < n; i++) { // 3 
        for (var j = 0; j < n; j++) { // 4
          sum = sum + i + j; // 5
        }
      }
    }

2行目はtの時間が必要で、3行目はn個のtの時間が必要で、4行目と5行目はそれぞれn 2個の時間が必要である.このコードの総実行時間は(2 n 2＋n＋1)＊tの時間である.
数学的な観点から,コードの全実行時間T(n)は各ラインのコードの実行回数に比例するという法則を導き出すことができる.
T(n)=O(f(n))
この式では、T(n)はコードの実行時間を表します.nはデータ規模の大きさを表します.f(n)は、行コード毎に実行される回数の総和を表します.Oはコードの実行時間T(n)がf(n)式に比例することを示している.
したがって、上記の2つの関数の実行時間をT(n)＝O(2 n＋1)とT(n)＝O(2 n 2＋n＋1)と表記することができる.これは大きいO時間の複雑さの表現法で、コードの本当の実行時間を代表しないで、コードがデータの規模の増加の変化の成り行きに従うことを表して、時間の複雑さを略称します.
またnが大きいときは定数項を無視して最大級だけを残してもいいです.上のコードの実行時間はT(n)=O(n)とT(n)=O(n 2)と簡単に表記できます.
時間の複雑さの分析
コードの時間の複雑さをどう分析すればいいですか?次の方法を利用できます.
1.循環実行回数が一番多いコードだけに注目してください.
私たちはコードの時間の複雑さを分析する時、循環回数が一番多いコードに注目すればいいです.例えば、第一段のコードの中で

function total(n) { // 1
      var sum = 0; // 2
      for (var i = 0; i < n; i++) { // 3
        sum += i; // 4
      } //5 
    } //6

3行目と4行目だけが実行回数が一番多く、それぞれn回実行すると定数項目を無視するので、このコードの時間的複雑度はO(n)です.
2.足し算の法則:総複雑度は最大級のコードの複雑さに等しい.
例えば、次のコードの時間の複雑さを見ます.

function total(n) { 
      //     for   
      var sum1 = 0; 
      for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
          sum1 = sum1 + i + j; 
        }
      }
      //     for   
      var sum2 = 0;
      for(var i=0;i<1000;i++) {
        sum2 = sum2 + i;
      }
      //     for   
      var sum3 = 0;
      for (var i = 0; i < n; i++) {
        sum3 = sum3 + i;
      }
    }

まずそれぞれのforサイクルの時間複雑さを分析して、その中の最大級を整理コードの時間複雑さとします.
第1段forサイクルの時間複雑度はO(n 2)である.
第二段forサイクルは1000回実行しました.定数レベルです.コードの実行時間に影響がありますが、n無限大の場合は無視できます.それ自体は成長傾向に影響がないので、このコードの時間的複雑さは無視できます.
第三段forサイクルの時間複雑度はO(n)である.
総体的には最大級をとるため、全セグメントコードの時間複雑度はO(n 2)です.
3.乗算の法則:ネストコードの複雑さはネスト内外コードの複雑さの積に等しい.
例えば、次のコードの時間の複雑さを見てください.

  function f(i) {
      var sum = 0;
      for (var j = 0; j < i; j++) {
        sum += i;
      }
      return sum;
    }
    function total(n) {
      var res = 0;
      for (var i = 0; i < n; i++) {
        res = res + f(i); //    f   
      }
    }

total関数を単独で見ると、時間の複雑さはT 1(n)＝O(n)であるが、f関数を考慮した時間の複雑さもT 2(n)＝O(n)である.したがって、全セグメントコードの時間複雑度はT(n)=T 1(n)*T 2(n)=O(n*n)=O(n 2)である.
いくつかのよくある時間の複雑さの分析
トップクラスの複雑さだけを見て、下の図の効率は逓減しています.上の図のように大まかに二つの種類に分けられます.
多項式級と
多項式級ではない.そのうち
非多項式級は二つしかありません.O(2)
n)O(n!)に対応する成長率を下図に示します.
データ規模nが増加すると、
非多項式級の執行時間は急激に増加します.
非多項式級のコードアルゴリズムは非常に非効率なアルゴリズムである.
1.O(1)
O(1)は、定数レベルの時間的複雑度表示法だけで、コードが1行しかないわけではありません.たとえば、次のようなコードです.

function total() {
      var sum = 0;
      for(var i=0;i<100;i++) {
        sum += i;
      }
    }

これだけ多くの行がありますが、forループが100回実行されても、コードの実行時間はnの増加に伴って増加しないので、このようなコードの複雑さはO(1)です.
2.O(logn)、O(nlogn)
対数の複雑さの共通コードは以下の通りです.

 function total1(n) {
      var sum = 0;
      var i = 1;
      while (i <= n) {
        sum += i;
        i = i * 2;
      }
    }
    function total2(n) {
      var sum = 0;
      for (var i = 1; i <= n; i = i * 2) {
        sum += i;
      }
    }

上記の2つの関数は同じ点を持っています.変数iは1から値を取ります.1サイクルに2を掛けます.nより大きい場合はループが終了します.実際、iの取得値は等比数列で、次のようになります.
20 21…2 k…2 x=n;
したがって、xの値を知ると、この2つの関数の実行回数が分かります.それは2 x＝nからx＝log 2 nを導出できるので、この2つの関数の時間複雑度はO(log 2 n)である.
次の二つの関数の時間の複雑さを見てください.

 function total1(n) {
      var sum = 0;
      var i = 1;
      while (i <= n) {
        sum += i;
        i = i * 3;
      }
    }
    function total2(n) {
      var sum = 0;
      for (var i = 1; i <= n; i = i * 3) {
        sum += i;
      }
    }

上から知ることができますが、この2つの関数の時間複雑さはO(log 3 n)です.
定数を無視できますし、対数の底数も無視できますので、対数の複雑さにおいては、O(logn)として統一的に表現されます.そのOの意味ははっきりしています.時間の複雑さはOのコードでn回も実行しました.
3.O(m＋n)、O(m＊n)
もう一つの特殊なコードの時間の複雑さを見てみます.例えば、

 function total(m,n) {
      var sum1 = 0;
      for (var i = 0; i < n; i++) {
        sum1 += i;
      }
      var sum2 = 0;
      for (var i = 0; i < m; i++) {
        sum2 += i;
      }
      return sum1 + sum2;
    }

私たちはmとnのサイズが大きいと評価できないので、その一つを無視することはできません.この関数の複雑さは2つのデータのレベルで決まるので、この関数の時間複雑さはO(m＋n)です.じゃ、O(m＊n)の時間の複雑さは似ています.
空間複雑度分析
空間の複雑さは時間の複雑さと似ていると推定すればいいです.空間複雑さとは、アルゴリズムの記憶空間とデータ規模との関係を表しています.
例えば、下記のコードの空間複雑度を分析します.

function initArr(n) {
      var arr = [];
      for (var i = 0; i < n; i++) {
        arr[i] = i;
      }
    }

時間の複雑さの推定によって、定数レベルを無視して、配列の割り当てごとに空間保存変数を申請しますので、この関数の空間複雑度はO(n)です.
一般的な空間複雑度はO(1)、O(n)、O(n 2)のみである.他はあまり使われません.
問題を解く
今から私たちは最初の思考問題に戻ります.コードの実現は簡単です.

function total(n) {
      var sum = 0;
      for (var i = 1; i <= n; i++) {
        sum += i;
      }
      return sum;
    }

この関数の時間の複雑さは、あなたが今すぐにわかるはずです.O(n)です.
この時間は複雑度が高いと思いますが、O(1)の時間複雑度関数がこのアルゴリズムを実現してもいいですか?
はい、小数学神通Gauss教会は次のように教えてくれます.

function total(n) {
      var sum = n*(n+1)/2
      return sum;
    }

この関数の時間の複雑さはO(1)だけです.データの規模が大きい場合、下の関数は明らかに上の関数よりも演算効率が高いですか?
締め括りをつける
複雑さも漸進複雑度といい、時間複雑さと空間複雑さを含み、実行の速度を表し、メモリの消費を表し、アルゴリズムの実行効率とデータ規模との成長関係を分析するために用いられ、高次複雑度のアルゴリズムほど、実行効率が低い.
複雑さの分析を学んだら、効率の低いコードを書くのは避けられますか?コードを分析してあげましょう.
重点
もし間違いや誤字があったら、メッセージで指摘してください.ありがとうございます.
また今度会いましょう.