big-o記号

bigoマーク法とは何ですか?

漸近表現法(漸近表現法)は,ある関数の成長形式を他の関数との比較で表す数論と解釈学の方法である.アルゴリズムを簡略化するための複雑さまたは無限級数の後部.その中で最も多く使われているのは大文字O,Big-Oである.このBig‐Oマーキング法は係数と低次項を排除する方法である.
アルゴリズムの評価には시간 복잡도と공간 복잡도を用い,時間的複雑度評価アルゴリズムの実行時間,空間的複雑度評価アルゴリズムの実行に必要なメモリ量を評価する.ここで、時間的複雑さと空間的複雑さは、主に以下のプレースホルダの1つであるbigoによって表される.これは,最悪の場合でもアルゴリズムの性能を測定するためにBigoシンボルを用いることができるからである.

大文字操作性能（実行時間、演算回数）

O(1) < O(logn) < O(n) < O(Nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)実行時間が最も短いO(1)のため、パフォーマンスはますます向上しています.時間の複雑さを低減できる場合は、プログラムのパフォーマンスが向上します.

時間の複雑さ

O(1)一定時間:nを考慮せずに1回に1つの演算のみを実行します.

O(log n)ログ時間:問題を解決するために必要なステップは、特定の要因によって減少します.

O(n)直線時間:問題を解決するには、Nを入力する手順が必要です.

O(Nlogn):問題を解決するために必要なステップの数はN回ごとに1つ減少し、N回ごとの数は特定の要因によって減少する.

O(n^2)2次時間:問題解決のためのステップ数は入力値nの二乗

O(2^n)指数時間:問題を解決するステップ数は、与えられた定数Cのn次方

である

くうかんふくざつさ

スペースの複雑さは、アルゴリズムで使用されるメモリの量を表します.空間複雑度は보조공간(Auxiliary Space)と입력 공간(input size)の総合概念である.アシストスペースは、アルゴリズムの実行時に使用される一時スペースです.したがって,入力空間(inputsize)は考慮されない.

スペースの複雑さの例(JavaScript)

function logUpTo(n) {
  for (var i = 1; i <= n; i++) {
    console.log(i);
  }
}

空間複雑度:O(1)

function logAtMost10(n) {
  for (var i = 1; i <= Math.min(n, 10); i++) {
    console.log(i);
  }
}

空間複雑度:O(1)

function logAtMost10(n) {
  for (var i = 1; i <= Math.min(n, 10); i++) {
    console.log(i);
  }
}

空間複雑度:O(1)

function onlyElementAtEvenIndex(array) {
  var newArray = Array(Math.ceil(array.length / 2));
  for (var i = 0; i < array.length; i++) {
    if (i % 2 === 0) {
      newArray[i / 2] = array[i];
    }
  }
  return newArray;
}

空間複雑度:O(n)

function subtotals(array) {
  var subtotalArray = Array(array.length);
  for (var i = 0; i < array.length; i++) {
    var subtotal = 0;
    for (var j = 0; j <= i; j++) {
      subtotal += array[j];
    }
    subtotalArray[i] = subtotal;
  }
  return subtotalArray;
}

空間複雑度:O(n)