TIL]CS 50-時間複雑度

9560 ワード
TIL 時間の複雑さ テキストリンク

🌼時間の複雑さ

시간 복잡도란 알고리즘을 수행할 때 걸리는 시간을 기준으로 효율성을 분석하는 것이다.時間の効率はアルゴリズムにおいて比較や交換などの操作が発生した場合、演算子の処理回数が少ないことを意味し、時間の複雑さが低いことを意味する.したがって,時間的複雑度が低いほど演算子の使用回数が少なくなり,アルゴリズムの効率が高くなる.ただ
  • 시간 복잡도 표기에 있어서 정확한 Running time을 계산하는 목적은 아니므로 상수는 생략한다.:Big-O 표기법:Big-O 표기법コンピュータ科学で「おおよそ」を表す正式な概念であり、최악의 경우에 대한 시간 복잡도를 나타내는 표현법이다.アルゴリズム性能の数学的表現である.対応する表現法を用いてアルゴリズムの時間,空間複雑度を表すことができる.ex) O(n + n) = O(2n) = O(n)
    • Q.泡順の最悪の場合、時間的複雑度はn^2である.それを証明してください.
    バブルソートを実行する場合は、n-1から1のソートを繰り返します.(n-1) + (n-2) ・ ・ ・ + 1
    これと等差数列の和式でわかりやすいです.
    S = (n-1) + (n-2) ・ ・ ・ + 1 ・・・ 1️⃣
    S=1+、・・・・(n-2)+(n-1)、・・・2ℋ
    1ネットワーク,2ネットワークの左項,右項をそれぞれ1つずつ加え,以下に示す.
    2S = n(n-1) → S = n(n-1)/2 → S = (n^2 - n)/2
    最終的な右式から時間複雑度を標準除去定数としてマークした場合、泡配列の大きなOはO(n^2)であった.
  • Big-Ω 표기법:: Big-Ω (omega) 符号あり、BigΩは いちばんよい 様子を表す.Bubbleソートでは,最適(ソートされた配列)を考慮すると,Bubbleソートは交換されなくてもソートの事実を知らないため,n−1回の比較が必要である.だから最良の場合はΩ(n)で表す.
  • Big-Θ 표기법:Big OとBigΩの共通部分で、最小と最悪の中間平均複雑度を示す.例えば、BigOとBigΩの時間的複雑度がn^2の場合、これを「」と表記することができる(n^2).

    • 🌼大きなO表現を用いて決定される時間複雑度のタイプ

  • ・O(1):入力データの大きさにかかわらず、常に一定時間のアルゴリズムが必要です.데이터의 크기와 성능이 비례하지 않는다 . 
    • function zero(arr) {
  return arr[0] === 0 ? true : false;
}
  • O(n):入力データのサイズによるアルゴリズム
    • function print(arr) {
  for (let i = 0; i < n; i++) {
    console.log(arr[i]);
  }
}
  • O(n²):入力データのサイズから値を算出し出力するアルゴリズム
    • function square(n) {
  for (let i = 1; i <= n; i++) {
    for (let j = i; j <=i; j++) {
      console.log(i * j);
    }
  }  
}
  • O(nm):入力した値が2つであれば、値の積で出力値を演算するアルゴリズム
    • function sum(a, b) {
  for (let i = 0; i < a; i++) {
    for (let j = 0; j < b; j++) {
      console.log(i + j);
    }
  }  
}
  • O(n³):入力データのサイズから値を算出し出力するアルゴリズム
    • function volume(n) {
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      for (let k = 1; k <= n; k++) {
         console.log(i * j * k);
      }
    }
  }  
}
  • O(2ⁿ):入力データの長さとデータの大きさ(指数時間)で出力値を演算するアルゴリズム

  • O(log n):アルゴリズムが多ければ多いほど、データ長の半分の実行回数が少なくなります.ありますlog n의 대표적인 알고리즘으로 Binary searchBinary searchの前提は、データが整列していることです.
  • O(sqrt(n)):正方形構造にデータを埋め込み、最上行のみを巡るアルゴリズム

    • 出典:YOUTUBE-エンジニア大韓民国、edwith-[海外名課]コンピュータ科学教育講座:CS 50
    Google Guavaの--cache
    Django Annotations and Aggregations