Time complexity

時間の複雑さ?

アルゴリズムの問題を解きながら効率的に解くことができるかどうか考えたことがある.これは時間の複雑さに悩むという意味です私はただ怠け者だからそう思っていると思っていましたが、これはもっと効率的な考え方で、よかったです.
では、時間の複雑さを考えると何を意味するのでしょうか.
入力値の増加または減少時間を比例的に増加または減少させる方法
ああ、つまり、ある関数が因子を50から100に増やしたとき、時間が同じ2倍なのか、異なる増加や減少なのかを見てみましょう.
だから私たちは効率的なアルゴリズムを作成するために、時間の複雑さで測定します.

Big-O??

Big−O表現は時間的複雑さを表す方法である.
このようにしたのは、万一に備えて最悪の状況を考えるためだ.
では、どのようなBig-Oマーク法がありますか?

O(1)

これは何ですか.入力値が増えるにつれて、時間は定数ですか?これは一定を意味する.したがって定数複雑度と呼ばれ,これは入力値が増加しても時間が増加しないことを意味する.例を挙げる

function constantComplexity(arr, index){
  return arr[index];
}
let arr = [1,2,3,4,5];
let index = 3;
let result = constantComplexity(arr, index);
console.log(result) // 4

上記の例では、変数arrの値が増加しても、出力値を直ちにロードできることを示しています.

O(n)

高校の数学の授業をたくさん思い出した.もちろん、経済数学の授業でも習ったことがあります.ハハハ.
O(n)は入力値が増加すると同じ割合で増加することを意味する.従って線形複雑度と呼ぶ.一般的にloopが1つあるとO(n)になります.もちろん、これはloopの使い方次第でしょうか?
例を挙げる

function linearComplexity(n){
  for(let i = 0; i < n; i++){
    // n이 늘어남에 따라 시간도 n이 늘어나는 비율로 늘어난다~
  }
}

O(log n)

これはログがあります対数複雑性と呼ばれています代表的な例としては、二元探索ツリー(BST)がある.テーブルで遊ぶUp&downゲームを考えてみればいいこれは意外にもこんなに効率的なゲームです...要するに,O(logn)の時間的複雑度はO(1)に次ぐ.

O(n^2)

感じました.これは入力値に比例し、時間が平方数に増加する可能性があります.正解!これを二次複雑性と呼んでいます
例を見てみましょう.

function quadraticComplexity(n){
  for(let i = 0; i < n; i++){
    for(let j = 0; j < n; j++){
      // 이건 계산을 n*n만큼 하기 때문에 시간도 걸린다. 
    }
  }
}

あ.ここで、n^3、n^4もO(n^2)と表記されている.理由はnが大きいほど指数の影響が小さくなるからである.

O(2^n)

これが一番遅いアルゴリズムだそうです.入力値が大きいほど不思議になるからです.指数的複雑さと呼ばれていますこのアルゴリズムの代表的な例として,再帰算されたフィボナッチ数列がある.
見せて見せてください.

function fibonacci(n){
  if(n<=1){
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

実際、ブラウザで返すと、コードの行数に比べて非常に長い時間がかかります.ほほほ

整理する

以上は高校の数学の授業です.久しぶりにアレンジし直した時にやっていて面白かったですその时私の数学もとても良いです...

時間の複雑さは最悪の状況に対応するために必要である.だからアルゴリズムを作るときは、この問題を考えなければなりません.より効率的なアルゴリズムを作成するために...