JavaScriptで学ぶアルゴリズム①[アルゴリズム基礎と線形探索]

外資系企業でソフトウェアエンジニアをしております、タロイモと言います。今日もよろしくお願いします。

今回から複数回に分けてアルゴリズムの勉強をしていきます。

第一回では「アルゴリズムとは何か」とO(1)、O(n)アルゴリズムを扱います。

アルゴリズムとは

そもそもアルゴリズムとはなんでしょうか。

アルゴリズムは計算方法と言えるでしょう。

国立情報学研究所の説明がすごく分かりやすかったので、
要約して紹介します。

参考：国立情報学研究所

人参で例えると、1本の人参を星形に30個に切るアルゴリズムは以下の2通りあるとします。

①一度30個に切って、星形に切る。

②一度星形に切って、30個に切る。

上記の2つはどちらが速いでしょうか。

当然、②ですよね。
②は、最初に一気に星形に切れば、あとは31個にするだけです。

(最初に包丁を10回通して、端っこを落とすために2回包丁を通し、29回人参に包丁を通すため、合計41回)

反対に①は、最初に30個に切ったら、それらを一個ずつ星形にする必要があります。

（最初に端っこを落とすために2回包丁を通し、29回人参に包丁を通す、一個の人参を星形にするために10回包丁を通し、それが×30なので、合計331回）

単純計算で、①は②の8倍近い時間がかかることになります。

コンピュータはとても計算が速いため、8倍だったらそんなに違いは感じられないでしょう。

しかし、それが100倍、1000倍、10000倍となるととんでもない時間になってしまいます。

このようにアルゴリズム（計算方法）を考え、計算実行時間を短くすることはとても大切なことです。

O(1)

O(1)のOは、O記法（オーダー記法）と呼ばれ、計算にかかる時間とデータの量の関係について表しています。

O(n)内のnにデータを与えた場合、そのアルゴリズムはどのくらいの時間がかかるかを表しています。

O(1)はnがありません。つまりどんなにデータが増えても計算は1回になります。

以下の関数にどんな言葉を入れても計算は1回だけなので、この関数はO(1)になります。
言葉の長さは関係ありません。

function greet(word) {
    console.log(word);
}

greet("こんにちは世界"); 
greet("hello world");
greet("おやすみなさい");

O(n)

O(n)は、データnが増えれば増えると、そのデータの数だけ計算量が増えていきます。

O(n)は線形探索とも呼ばれます。

一列のデータ（線）を1つずつ調べていくことが由来です。

function linear_search(key, array) {
   for (let i = 0; i < array.length; i++) {
       if (array[i] === key) {
          console.log(`${key} は存在します。`);
       }
   }
}

let array = [1, 2, 5 ,7, 8, 10, 11, 18, 21]; 

linear_search(2, array); //2は存在します。 
linear_search(3, array); //（出力なし）
linear_search(13, array); //（出力なし）

function linear_searchの中のfor文は、配列の長さ(array.length)の分だけデータを調べるので、配列が長くなるにつれて計算量が増えます。

今回では配列の長さがnに当てはまるので、n = 9となります。

今回はアルゴリズムとは何かについて、そして簡単なアルゴリズムについてO記法（オーダー記法）で紹介しました。

ご精読ありがとうございました。