Big-Oマーキング法とは?

コンピュータサイエンス(Computer Science)では、アルゴリズムはいかなる問題を解決する方法であり、いかなる問題を解決する方法は多種多様であるため、通常、大きなO(big-O)タグを用いて方法(アルゴリズム)間の効率を比較する.

「コードを作成する」とはどういう意味ですか?

コードの処理速度はもっと速いですか?(Faster)

コードの消費メモリは少ないですか?(Less memory-intensive)

コードの読み取り可能性は良いですか?(More readable)

コード行は短いですか?

以上の4つの状況はいずれも一定の重要性があるが、1-2号は3-4号よりも重要である.(コードが長く、可読性が悪いと良いコードではない)だからメモリを迅速かつ効率的に使用し、可読性の良いコードを書くのが一番だと思います.

アルゴリズムの時間的複雑さ

アルゴリズムの複雑度を判断する尺度には時間複雑度と空間複雑度の2種類があり,bigo表現法は時間複雑度に関与する.もちろん,アルゴリズムの演算量が大きいほど速度が速くなる.従って,時間複雑度はアルゴリズムでの演算回数に関係する.
簡単に言えば、演算が多くなると時間の複雑さが大きくなります.と理解できる.

時間の複雑さを計算する方法

いろいろな方法がありますが、一番簡単な方法timing functionを使います.これはアルゴリズムの中でどのアルゴリズムがもっと速いかを計算する方法です.
例を挙げて、すべての数字を加算します.

// 알고리즘: 모든 숫자 더하는 함수
function addUpToA(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
  	total += i;
  }
  return total;
}

// timing function 활용하여 시간 계산
let t1 = performance.now();
addUpToA(100000000);
let t2 = performance.now();
console.log(`걸린 시간: ${(t2 - t1) / 1000}초`)

걸린 시간: 0.09819999998807907초

実行するたびに、わずかな値が異なる場合があります.毎回違う方法で演算するからです.でも小さな差だから気にしなくていいまた、実行するコンピュータのパフォーマンスが異なる場合があります.これも重要ではありません.
ここで重要なのは、さまざまなアルゴリズムの演算速度を比較できることです.結果は同じですが、異なる方法(アルゴリズム)で書かれたコードと比較します.

function addUpToB(n) {
  return n * (n + 1) / 2;
}

let t1 = performance.now();
addUpToB(100000000);
let t2 = performance.now();
console.log(`걸린 시간: ${(t2 - t1) / 1000}초`)

걸린 시간: 0초 (진짜 0초는 아니고 거의 0초)

addUpToAおよびaddUpToBは同じ結果を示した.ただし、この2つのコードを別々に実行すると、addUpToBよりもはるかに速い時間がかかります.結果は同じであるが、addUpToBはaddUpToAよりも優れたアルゴリズムである.
しかし、timing functionの方法でコード比較を簡単に行うことができますか?100%じゃないよ理由を言えば.
各

装置は、異なる方法で時間を記録する.

のような装置であっても、異なる時間を記録することができる.

高速アルゴリズムでは、処理時間が短く、精度が低い.

サイズが大きすぎると、対応する方法で確認するのは難しい.

これらのため、実際に使うのは難しい.timing functionの方法は単純な方法にすぎない.これらの困難を解決するためにbigo記号を使用することができます.

解決方法：大きいO記号

上記の簡単な時間測定問題を解決する方法.Bigoシンボルは、コンピュータが処理しなければならない演算の数を数えることによって時間を測定する.この方法はコンピュータの性能にあまり影響しない.addUpToAとaddUpToBをbikoマーキング法で比較した.

addUpToA : O(n)

addUpToB : O(1)

addUpToAはO(n)であり、入力数が多ければ多いほど演算量が大きくなるからである.for문はO(1)であり,入力数が多くなっても演算は変わらないからである.

時間複雑度の高速順序

時間の複雑さの順序は次のとおりです.
O(1) > O(logn) > O(n) > O(nlogn) > O(n^c) > O(c^n) > O(n!)addUpToAはO(n)であり、addUpToAはO(1)であるため、より高速である.

ビオマーク法の特徴

bigoタグ法を使用する場合は注意が必要です.

O(2) → O(1)

O(2n) → O(n)

O(3n^2 + 2n + 3) → O(n^2)

定数アイテムを削除し、サブアイテムを削除する必要があります.

最後に。

バックアップの準備が終わった私にとって、これは理解しなければならない概念だと思います.いくつかの問題にとって、アルゴリズムの時間の複雑さが低いほど、アルゴリズムの効率が高くなるからです.
オンライン障害の問題を解決するだけでなく、問題を理解し、解決する過程が重要だと思います.

REFERENCE

udemy javascript algorithm