時間の複雑さと空間の複雑さの計算方法

アルゴリズムとは
アルゴリズムの定義はこのようなものである.ソリューションの正確かつ完璧な説明は、一連の問題解決のための明確な命令である.バラバラの、短い文章ですが、見たくないです.つまり、問題の完全性を解決するための記述です.ただ、この説明は違った方式、あるいは「言語」を使っているかもしれません.
アルゴリズムの効率
アルゴリズムが問題を解決する説明である以上、千人の目の中に千人のアムレートのおばさんがいるように、同じ問題を解決する方法も多種多様であり、この過程で私たちが使っている/消費している時間または時間以外の価格(計算機が消費しているのはメモリです)は違っています.オレオをより速く、より良く、より強く発揚するために.いや、アルゴリズムの効率を向上させます.したがって、多くの場合、優れたアルゴリズムは、他の同じ問題を実装するアルゴリズムと比較して、時間または空間(メモリ)または時間と空間(メモリ)において明らかに低減される.
したがって、アルゴリズムの効率は主に以下の2つの複雑さによって評価される.
 
時間複雑度:プログラムの実行に必要な時間を評価します.プログラムのプロセッサへの使用度を推定することができます.
空間複雑度:実行プログラムを評価するために必要な記憶空間.プログラムのコンピュータメモリの使用度を推定することができます.
 
アルゴリズムを設計する時、時間の複雑さは空間の複雑さより問題が発生しやすいので、普通は時間の複雑さだけを研究します.面接や仕事の時に特に説明がないと複雑さとは時間の複雑さのことです.
1.0空間複雑度一つのプログラムの空間複雑度とは、一つのプログラムを実行し終わるために必要なメモリの大きさをいう.プログラムの空間複雑さを利用して、プログラムの実行に必要なメモリの数を予め見積もることができます.プログラム実行時には、自分が使用するコマンド、定数、変数、および入力データを格納する必要があるほか、データを操作するワークユニットや、現実計算に必要な情報を格納するための補助空間が必要です.プログラム実行時に必要な記憶空間は、以下の2つの部分を含みます.(1)固定部分.この部分の空間の大きさは、入出力データの個数の多少、数値とは無関係です.主に指令空間(すなわちコード空間)、データ空間(定数、単純変数)などが占める空間を含む.この部分は静的空間に属する.(2)可変空間、この部分の空間は主に動的に割り当てられた空間、及び再帰的なスタックに必要な空間などを含む.この部分の空間サイズはアルゴリズムと関連している.アルゴリズムに必要な記憶空間はf(n)で表される.S(n)＝O(f(n))ではnが問題の規模であり、S(n)は空間複雑度を表す.
2.0-時間複雑度
次にもう一つの概念を知る必要があります.時間の頻度.この時、「アルゴリズムを一緒に勉強すると約束したじゃないですか?これらのものは何ですか?贈り物ですか?」これは非売品です.
アルゴリズムの実行によって消費された時間は理論的に計算できないので、間違いなく理論的に、そして私達は任意にプログラムでテストして獲得することができます.しかし、各アルゴリズムをテストする必要はありません.大体どのアルゴリズムが実行するのにかかる時間が多いかを知るだけで、どれがかかるか時間が少ないだけでいいです.一つのアルゴリズムが費やす時間がアルゴリズムのコードステートメントの実行回数に比例するなら、そのアルゴリズムはステートメントを実行するほど多くなり、その時間も多くなります.アルゴリズム中のステートメントの実行回数を時間頻度と呼びます.通常はT(n)で表されています.
時間周波数T(n)において、nはまた問題の規模を表しており、nが継続的に変化すると、T(n)も絶えず変化する.この変化の法則を知るために,時間複雑度という概念が導入された.一般的に、アルゴリズムは、本動作の繰り返し実行回数に基づいて、問題規模nのある関数、すなわち時間頻度T(n)を使用する.ある補助関数f(n)がある場合、無限大になるとT(n)/f(n)の限界値はゼロではないある定数である.f(n)はT(n)の同数級関数であり、T(n)=O(f(n))と記載され、アルゴリズムの漸進時間複雑度とも呼ばれ、時間複雑度とも呼ばれる.
2.1-大O表示法
O(n)を使ってアルゴリズムの時間複雑さを表現する表記は大O表示法と呼ばれています.
一般的にアルゴリズムを評価し,その最悪の複雑さを直接評価した.
大O表現法O(f(n))におけるf(n)の値は、1、n、logn、n^2などとすることができるので、O(1)、O(n)、O(logn)、O(n^2)をそれぞれ定数次数、線形次数、対数次数、および二乗と呼ぶ.大きなO次を導出する方法を見てみましょう.
大O次を導出
大Oランクを導くには以下の3つの規則があります.

運転時間の加算定数を定数1で置き換える

最高レベルのみを保持する

.

は、最上位の定数

を除去する.
くりをたくさんあげる

定数レベル

let sum = 0, n = 10; //        
let sum = (1+n)*n/2; //        
console.log(`The sum is : ${sum}`) //       

このようなセグメントコードの実行回数は3回で、規則1を適用すると、このアルゴリズムの時間複雑度はO(1)、つまり定数次数となります.
また、例えば、アルゴリズムの実行時間が問題規模nの増加に伴って増加しない場合、アルゴリズムの中に千個以上の語句があっても、その実行時間は大きな定数に過ぎない.このようなアルゴリズムの時間複雑さはO(1)である.x=91;y=100;while(y>0)if(x>100){x=x-10;y–;else x+;;答え:T(n)=O(1)、このプログラムはちょっと怖いように見えます.全部で1000回循環しましたが、nは見ましたか?このプログラムの実行はnとは無関係で、たとえそれがもう一万年サイクルしても、私達は彼を無視して、ただの定数の次数の関数です.

リニアレベル

let i =0; //        
while (i < n) { //     n  
  console.log(`Current i is ${i}`); //    n 
  i++; //     n 
}

このアルゴリズムでコードは3 n＋1回実行され、規則2->3に従って、このアルゴリズムの時間複雑さはO(n)である.

対数階

let number = 1; //        
while (number < n) { //     logn 
  number *= 2; //     logn 
}

上記のアルゴリズムでは、numberは毎回2倍に拡大されており、この循環体がm回実行されたと仮定すると、2^m = nすなわちm = lognであるので、セグメントコード全体の実行回数は1＋2＊lognであると、f(n) = lognで、時間の複雑度はO(logn)である.

平方階

for (let i = 0; i < n; i++) { //     n  
  for (let j = 0; j < n; j++) { //     n^2  
     console.log('I am here!'); //     n^2
  }
}

上のネストループでコードが2＊n^2＋nを実行するとf(n) = n^2です.このアルゴリズムの時間複雑度はO(n^2)です.
例えば、いくつかの循環文がある場合、アルゴリズムの時間複雑度は、ネスト層数が最も多い循環文の中で最も内層文の頻度f(n)によって決定される.x=1;for(i=1;i==n;i＋＋)for(j=1;j==i;j+)for(k=1;k==j;k+)x+;このプログラムの中で頻度が一番大きい語句は(5)であり、内部循環の実行回数は問題規模nと直接関係がないが、外層循環の変数の値と関係があり、最も外層循環の回数は直接nと関係があるので、内層循環から外層分析語句(5)の実行回数は、このプログラム期間の時間複雑度はT(n)＝O(n 3/6＋低次項)＝O(n 3)である.
よくある時間の複雑さの比較
O(1)
転載先:https://zhuanlan.zhihu.com/p/32135157