時間の複雑さ

時間複雑度とはアルゴリズムの実行速度を指す
アルゴリズムは,1つの問題を解く際に複数のコードを用いて解くことができる.
問題を解く方法はいろいろあるが,実行速度が最も遅い最適コードを記述することは有効であるため,アルゴリズムを記述する際のこの時間的複雑さの重要性が高まる.
このような時間の複雑さを私たちの日常生活にたとえて、私たちにもっと理解しやすいようにします.

約束の前に、龍仁から水原まで車に乗ったとします.
移動時間は全部で1時間30分かかりました.グーグルが教えてくれた最短ルートに行ったら、1時間以内に着きます.大切なデートの30分前が大切なので、次回から効率よく時間を使います.
コンピュータプログラミングにおいても,時間的複雑度が最も低いアルゴリズムを用いてこの状況を改善した.上記の例に示すように、龍仁から水源までタクシーに乗るステップをアルゴリズムと呼び、実行される演算数を時間複雑度と表す.以上の例をアルゴリズムで以下に示す.

function TakeCar(from, to){
  /*
  1. 차에 탑승한다
  2. 차 시동을 건다
  3. 용인에서 수원까지 운전한다
  4. 차 시동을 끈다
  5. 차에서 내린다
  */
}

上で一番時間がかかるのは何ですか?
もちろん3日が一番長くかかります.コードを記述しても時間の複雑さを計算できるので、最も時間がかかるのは、上記の例では、3回の時間を短縮することが時間の複雑さの核心である.
時間的複雑さは一般に漸近マーキング法として用いられ,主に用いられる漸近マーキング法は以下の3つである.

Big-O表現/O(N):Big-O表現アルゴリズム최악の実行時間

Ω表現/Ω(N):ω表現アルゴリズム최상の実行時間

Θ 記号/Θ(N):三打法表示アルゴリズム평균実行時間

以上の3つの一般的な漸近線マーキング法はBig-Oマーキング法であり,より詳細に説明する.

ビオ記号法

不要な演算を排除し、アルゴリズム分析を簡素化するための時間複雑度パフォーマンスタグ
Big-Oは時間の複雑さを表す記号の一つであり、「O(入力)」で表される.bigoマーキング法の性能順序は以下のようにすることができる.

一番左のO(1)は、運転回数が少ないほど/時間の複雑さが低くなり、一番右のO(n!)実行回数の増加/時間の複雑さはますます高まっていると言える.
O(1)一定時間
:アルゴリズムが実行する演算は入力とは無関係です.つまり、入力データの大きさにかかわらず、一定の時間が必要となる.

function BigO(n){
  console.log("Hello Big-O");
}

O(n)線形時間
:アルゴリズム入力を実行する個数n.すなわち,入力データが多ければ多いほど処理時間が長くなる.

function BigO(n){
  for(let i=0; i<n; i++){
    console.log(i);
  }
}

O(n^2)次時間
:アルゴリズムを実行して個数のn^2を入力します.すなわち,入力データが多ければ多いほど処理時間が2倍になる.

function BigO(n){
  for(let i=0; i<n; i++){
    console.log(i);
      for(let j=0; j<n; j++){
    	console.log(j);
      }
   }
}