big-o表現時間複雑度表現法

TOC

時間の複雑さとは?

O(1)

1.時間の複雑さとは？

時間複雑度とは計算複雑度理論において,時間複雑度とは問題を解決するのに要する時間と入力の関数関係を指す.ソース:ウィキペディア
入力による問題解決に要する時間の関数関係と見なすことができる.
まずは最も簡単な時間の複雑さから確認しましょう.

O(1)

図からO(1)の図は時間に垂直な図であることがわかる.
配列のサイズにかかわらず、配列インデックスの0番目の値を決定します.
入力にかかわらず、時間には一定の時間複雑度があります.

// O(1)
const Oone=(ary)=>{
	return ary[0]===0 ? true : false;
}

写真ソース

O(n)

const On=(number)=>{
	for(let i=0; i<number;i++){
    	if(i===number) return i;
    }
}

上記の関数はO(n)の時間的複雑さを有する.
なぜなら、入力値numberのサイズが大きいほど、検索された値は0からnumberになるからです.
i数字の大きさによって時間がかかるので、直線図を描きます.
写真ソース

O(n^2)

const OnSquare=(ary)=>{
	for(let i=0;i<ary.length;i++){
    	for(let j=0;j<ary.length;j++){
        	console.log('i, j',i,j);
        }
    }
}

写真ソース
この関数はO(n^2)の時間的複雑さを持つ.

nに対してnの

を繰り返す
入力値がarrayで長さが3の場合
最初のアレイでは、重複文の長さはアレイの長さと同じです.[0]2番目のアレイで動作する時間は[2]と同じくらい多い
また、関数の処理を完了するには[2][2]に達するまでこの操作を繰り返さなければならないので、正方形の形状は:
O(n^2)の時間的複雑さといえる.
写真ソース
平方なので二次関数図を描きます.

O(nm)

const Onm=(aryN,aryM)=>{
	for(let i=0;i<aryN.length;i++){
    	for(let j=0;j<aryM.length;j++){
        	console.log('i, j',i, j);
        }
    }
}

上記のコードは前に見たO(n^2)と類似している.
違いは

nに対してmの

を繰り返す
すなわちnとmは異なる数である.mの値が大きくなると、nループがmを待つ時間が増えるでしょう?
逆に,mの値が小さい場合,nはmのループ終了に飽きない.
この記号はグラフィックにない場合があります.グラフィックの形状はmの値によって変わります.n>mの場合、O(n^2)のパターンの幾何級数上昇区間はさらに後方に遅延する.n=mの場合、O(n^2)のパターンと同じです.n<mであれば、O(n^2)の図形よりも早い幾何級数が上昇する.

O(n^3)

const Ocube = (ary)=>{
	for(let i=0;i<ary.length;i++){
    	for(let j=0;j<ary.length;j++){
        	for(let p=0;p<ary.length;p++){
            	console.log('i, j, p',i,j,p);
            }
        }
    }

}

以上のコードはO(n^3)の時間的複雑さを表す.
直線=>平面=>立体の長さ.
配列の長さで3回働くのでO(n^3)の形を持つ.
写真ソース

O(2^n)

const fibo=(n)=>{
  
	if(n<=0) return 0;
  	else if(n<2) return n;
  	return fibo(n-1)+fibo(n-2);
}

フィボナッチ数列の再帰関数の実装では,時間複雑度はO(2^n)の時間複雑度を有する.
なぜなら,2回の再帰関数が呼び出されるため,理解に役立つ視覚資料から見ると,理解がより容易であるからである.

ソース
写真を見ると、1回の関数呼び出しで2つの再帰が発生するため、2^nほど多くのことが発生します.
注記後のコードは以下の通りです.

let f = [];

let fibo = (n) => {
  if (f[n] !== undefined) {
    return f[n];
  } else {
    if (n === 1 || n === 2) {
      f[n] = 1;
    } else {
      f[n] = fibo(n - 1) + fibo(n - 2);
    }
    return f[n];
  }
};
console.log(fibo(6));

写真ソース
グラフは2^nよりも悪いパフォーマンスを示していますが、なぜこの再帰を使用するのでしょうか.
現在コメントを使用していない場合は、コメントは使用しないほうがいいです.

高速O記号

O(log n)

const binarySearch = (key, arr) => {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const guess = arr[mid];

    if (guess === key) return mid;
    if (guess > key) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return null;
};

console.log(binarySearch(4, [2, 4, 6, 7, 8, 10, 22]));

代表的な例はバイナリサーチまたはバイナリサーチまたはバイナリサーチ...待ってる名前がある
もしこの人が李辰探索だけを知っていたら何ですか?これでは困ります
要するに、上記のコードは、lowから(またはstart)high(またはend)までの中間値mid値が検索中のキー値と一致するかどうかを調べるために昇順配列の配列を受け入れ、キー値がmid配列の推測値より大きい場合、low値をmid+1に引き上げ、mid以下の値が閲覧されないようにする.
計算する
最初の入力配列の個数はnである.
検索する最初の対称配列の数はn 2frac{n}{2}2 nである.
見つからない場合は、2番目の対称n 2frac{n}*frac{1}{221を再使用します.
見つけるまで繰り返しますので整理しておきます
n 2=12nfrac{n}=frac{1}*n 2 n=21nとなるためnは除外され,重複する12frac{1}{2}21にkが乗じられる.
(12)kn(frac{1}{2})^kn(21)knはこのようにして生じる.
このとき
k=binarySearchの実行回数.
n=配列の個数
これは、検索する配列数が12frac{1}{2}21減少し続けることを意味します.
配列の長さが1の場合、keyに一致する値が見つかります.
(12)kn=1(frac{1}{2})^kn=1(21)kn=1=終了
これはnn値に12frac{1}{2}21に何回1を乗じたかを知るプロセスである.
儀式を再利用すると.
(12)kn=1(\frac{1}{2})^kn=1(21)kn=1.ここに2 k 2^k 2 kを乗じて左はnのみ、右は2 k 2^k 2 kとなります.
n=2 kn=2^kn=2 kこれをログ表示とし、下部2の高さ2をnとする指数kを示す.
log2n=klog_2n=klog2​n=k
このうち2は通常省略されます.
したがって、O(log) n)O(log\n)O(log n).
k=binarySearchの実行回数であるため、logとして表すことができる.
写真ソース
図形が見える場合、O(logn)は要求に合致する速度を表す.
big-o記号は、上記のログ計算の定数を破棄します.
理由はアルゴリズムの時間を計測するためではなく,アルゴリズムを用いた場合の変数による時間成長率である.
これは確認のための表記法だからです.
定数は常に定数の増分で表示されるので、すでに固定値です.したがってbig-o符号では省略する.
これらを知っていても大丈夫でしょうか?