アルゴリズムとは?

問題をどのように解決するかを定義できます.

じかんふくざつせい

有効な方法を考えるのは時間の複雑さを考えることに等しい.
入力値の増加/減少に伴って時間の複雑さがどのくらい増加/減少するかを考慮します.に整理できます.
すなわち、前述した効率的なアルゴリズムを実現し、言い換えれば、入力値の増大に伴って増加する時間パーセンテージが最小となるアルゴリズムを構成している.

Big-O記号

時間の複雑さを表す方法では、

Big-O

Big-Ω

Big-Θ
あります.
最悪、最良、中等(平均)の場合、入力値が増加するにつれて時間の複雑さはどのくらい増加しますか.
その中で最もよく使われるのがBig-Oマーキング法です.

「少なくともこの時間が必要」とか「こんなに長い時間が必要」という考えは興味深い.「こんなに時間がかかるかもしれない」と考えてこそ、対応できる.

最悪の場合が起こらないことを願って、時間を計算するよりも、最悪の場合を考えたほうがいいです.

Big-Oシンボルのタイプ

O(1)

O(1)はConstant複雑性と呼ばれ,これは入力値が増加しても時間が増加しないことを意味する.
すなわち、入力値がどんなに大きくても、直ちに出力値を得ることができる.

O(1)時間の複雑さを持つアルゴリズム

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

上記のアルゴリズムでは,入力値の大きさにかかわらず,直ちに出力値を得ることができる.
たとえばarrの長さが100万の場合、すぐにインデックスにアクセスし、値を返します.

O(n)

O(n)は線形複雑度と呼ばれ,入力値が増加するにつれて時間も同様の割合で増加することを意味する.
例えば、入力値が1の場合に1秒、入力値が100の場合に100倍の100秒を要するアルゴリズムが実現されると、このアルゴリズムはO(n)の時間的複雑さを有する.

O(n)時間の複雑さを持つアルゴリズム

function O_n_algorithm(n) {
  for(let i - 0; i < n; i++) {
    // do something for 1second
  }
}
function another_O_n_algorithm(n) {
  for(let i = 0; i < n; i++) {
    // do something for 1second
  }
}

O n algorithm関数では,入力値(n)が1増加するごとにコード実行時間が1秒増加する.
すなわち、入力値が増加するにつれて、同じ割合でかかる時間が増加している.
other O n algorithm関数は入力値を1秒増加するごとにコードの実行時間を2秒増加させる.
O(2 n)で表されると考えられるが,このアルゴリズムもO(n)で表される.
同じ比率で増えれば、2倍でなくても5倍、10倍とO(n)で表される.

O(log n)

O(logn)は対数複雑度と呼ばれ,Big‐Oマーキング法ではO(1)に次ぐ高速時間複雑度を持つ.
BSTでは,必要な値にナビゲートすると,ノードを移動するたびに状況の数が半分に減少する.
up/downゲームの例を挙げることができます.
1つの数字を出すたびに、状況の数は半分に減少します.

O(n^2)

O(n^2)は二次複雑性と呼ばれ,入力値が増加するにつれて時間がその平方数の割合で増加することを意味する.
例えば、入力値が1の場合、1秒を必要とするアルゴリズムに5の値が与えられ、25秒を必要とする場合、そのアルゴリズムの時間複雑度はO(n^2)と表される.

O(n^2)時間の複雑さを持つアルゴリズム

function O_quadratic_algorithm(n) {
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
      // do something for 1second
    }
  }
}
function another_O_quadratic_algorithm(n) {
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
      for(let k = 0; k < n; k++) {
        // do something for 1second
      }
    }
  }
}

2 n,5 nともにO(n)と表され,同様の脈絡,n^3,n^5も無頭big-Oの表現法であり,O(n^2)を表す.

O(2^n)

O(2^n)は指数複雑度と呼ばれ,Big−Oマーキング法では最も遅い時間複雑度を持つ.
折り紙を例にとると、折り紙の厚さが2倍になることを意味します.

O(2^n)時間の複雑さを持つアルゴリズム

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

再帰的に実現したフィボナッチ数列は代表的なO(2^n)時間複雑度を持つアルゴリズムである.