アルゴリズムの学習を改めてしたので学んだことをまとめました。
アルゴリズム
アルゴリズムの性能を評価するためには計算量という指標が用いられる。アルゴリズムのパフォーマンスは使っているデータの種類など、様々な要因が影響するためパフォーマンスを評価する際は最良、最悪、平均的な場合の計算量を考慮するべきである。
計算量には時間計算量と領域計算量(空間計算量)があり、時間計算量は処理時間がどれだけかかるのかを表し、領域計算量はどれだけの記憶容量を必要とするかを表す。多くの場合、単に計算量というと時間計算量の方を指す。
コンピューターはメモリーのような有限なリソースを備えているためアルゴリズムの時間計算量に加えてリソースの使い方も考慮しなければならない。
-
領域計算量アルゴリズムに必要なメモリー領域の大きさで、静的領域、データ構造領域、一時領域を含む -
静的領域プログラムに必要なメモリーの量 -
一時領域アルゴリズムが中間処理をするのに必要なメモリーの量
操作の実行時間
計算量の記述にはO記法という表記が使用される。(OはOrder)
実行されるアルゴリズムが、どれほどの時間、記憶領域を使用するかを評価するも基準として用いられる。
- 平均 * 基本的に最悪を想定する
| データ構造 | アクセス | 探索 | 挿入 | 削除 |
|---|---|---|---|---|
| 配列 | O(1) | O(n) | O(n) | O(n) |
| スタック | O(n) | O(n) | O(1) | O(1) |
| キュー | O(n) | O(n) | O(1) | O(1) |
| 連結リスト | O(n) | O(n) | O(1) | O(1) |
| ハッシュテーブル | N/A | O(1) | O(1) | O(1) |
| 二分探索木 | O(logn) | O(logn) | O(logn) | O(logn) |
- 最悪
| データ構造 | アクセス | 探索 | 挿入 | 削除 |
|---|---|---|---|---|
| 配列 | O(1) | O(n) | O(n) | O(n) |
| スタック | O(n) | O(n) | O(1) | O(1) |
| キュー | O(n) | O(n) | O(1) | O(1) |
| 連結リスト | O(n) | O(n) | O(1) | O(1) |
| ハッシュテーブル | N/A | O(n) | O(n) | O(n) |
| 二分探索木 | O(n) | O(n) | O(n) | O(n) |
- 探索、ソートの計算量
| 処理 | 計算量 |
|---|---|
| 定数 | O(1) |
| 線形探索 | O(n) |
| 二分探索 | O(logn) |
| クイックソート, マージソート | O(nlogn) |
| バブルソート,挿入ソート,選択ソート | O(n^2) |
| 二分探索木 | O(n) |
探索
線形探索
線形探索はO(n)かかる。
const numberList1 = [2,546,12,67,23,11]
const numberList2 = [1,4,10,33,56,78]
const linearSearch = (list, target) => {
for (const n of list) {
if (n === target) return true
}
return false
}
console.log(linearSearch(numberList1, 10)) // false
console.log(linearSearch(numberList2, 10)) // true
二分探索
ソート済みの時に使える。
二分探索はO(logn)で線形探索より効率的。
中央値を探し、探している値が中央値より大きいか小さいかを比較し探索する範囲を半分に絞る→次の探索でさらに半分に絞る...という具合に探索する方法。
const numberList1 = [2,11,22,32,52]
const numberList2 = [1,4,10,33,56,78]
const binarySearch = (list, target) => {
let first = 0
let last = list.length - 1
while (last >= first) {
console.log(list[mid]);
if (list[mid] === target){
return true
} else {
if (target < list[mid]) {
last = mid -1
} else {
first = mid + 1
}
}
}
return false
}
console.log(binarySearch(numberList1, 10)) // false
console.log(binarySearch(numberList2, 10)) //true
ソート
バブルソート
任意の数字のリストに対して隣接する２つを比較し順番になるように入れ替える作業を繰り返す。
バブルソートは安定ソートでもありソートするためのルール以外では最初の並びを保持する。逆に不安定ソートは並び替えが起こる前の並び順に保証がないソート。
時間計算量はO(n^2)
//ソート前の配列データ
const numberList = [7, 3, 10, 5, 1];
const bubbleSort = (list) => {
for(let outer = 0; outer < list.length -1; outer++){
for(let i = list.length-1; i > outer; i--){
if(list[i] < list[i-1]){
let tmp = list[i];
list[i] = list[i-1];
list[i-1] = tmp;
}
}
}
return list
}
console.log(bubbleSort(numberList)); // [1, 3, 5, 7, 10]
挿入ソート
配列から値を取り出し、その値を正しい位置に移動させていくソートで手札のトランプを整列させていくようなアルゴリズム。
挿入ソートも安定ソート。時間計算量はO(n^2)
const insertionSort = (list) => {
for (let i = 1;i<list.length;i++) {
let value = list[i]
while (i > 0 && list[i -1] > value) {
list[i] = list[i-1]
i = i-1
}
list[i] = value
}
return list
}
console.log(insertionSort([2.6,2,65,34,43,7,4,1]))
// [1,2,2.6,4,7,34,43,65]
マージソート
要素が一つだけ含まれるリストになるまでリストを半分ずつに分け続け、その後正しい並びになるように整列しながら統合していくアルゴリズム。分割統治法の1つ。
サブリストに分割するのは計算時間量lognだが1つのリストに統合する作業は線形時間量nが必要なためO(nlogn)となる。
const mergeSort = (list) => {
if (list.length < 2) {
return list;
}
let middle = Math.floor(list.length / 2);
const left = list.slice(0, middle);
const right = list.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
const merge = (left, right) => {
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
console.log(mergeSort([2.6,2,65,34,43,7,4,1]))
// [1,2,2.6,4,7,34,43,65]
クイックソート
配列の中で小さいデータを左、大きいデータを右に集める。これを繰り返すことで順番に並べる。
ピボットとする値によって計算量が変わってくる。
const quickSort = (list) => {
if (!list.length) {
return list;
}
const pivot = list[0];
const minArr = list.filter(list => list < pivot);
const maxArr = list.filter(list => list > pivot);
return [...quickSort(minArr), pivot, ...quickSort(maxArr)];
}
console.log(quickSort([8,41,6,4,2,19]))
選択ソート
配列を線形探索し最小値を探して、先頭から順番に並べていく方法
const searchMinIndex = (
list,
minIndex,
curIndex
) => {
if (curIndex === list.length) {
return minIndex
}
if (list[minIndex] > list[curIndex]) {
minIndex = curIndex
}
return searchMinIndex(list, minIndex, curIndex + 1)
}
const _selectionSort = (list, start) => {
if (start === list.length) {
return list
}
let minIndex = searchMinIndex(list, start, start)
let tmp = list[start]
list[start] = list[minIndex]
list[minIndex] = tmp
return _selectionSort(list, start + 1)
}
const selectionSort = (list) => {
const start = 0
return _selectionSort(list, start)
}
console.log(selectionSort([3, 4, 6, 5, 3, 88, 90, 0])) // [0, 3, 3, 4, 5, 6, 88, 90]
データ構造
連結リスト
連結リストはリスト抽象データ方の実装の1つ。要素は連結したノードで構成されている。ノードのメモリーアドレスは連続しておらず、それぞれのノードが値と次のノードの位置を持つ。このため要素はインデックスがない。
最初のノードをヘッドと呼び、各ノードが持つ次のノードの位置のことをポインターと呼ぶ。
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
size() {
let counter = 0;
let node = this.head;
while (node) {
counter++;
node = node.next;
}
return counter;
}
getLast() {
return this.getAt(this.size() - 1)
}
getAt(index) {
if (!this.head) {
return null;
}
let counter = 0;
let node = this.head;
while (node) {
if (counter === index) {
return node;
}
counter++;
node = node.next;
}
return null;
}
insertAt(data, index) {
// 空のリストにノードを追加する場合
if (!this.head) {
this.head = new Node(data);
return;
}
if (index === 0) {
this.head = new Node(data, this.head); // 前のheadをnextにする
return;
}
// リストの中、最後にノードを追加する場合
const previous = this.getAt(index - 1) || this.getLast();
previous.next = new Node(data, previous.next);
}
}
const linkedList = new LinkedList()
linkedList.insertAt('abc', 0)
linkedList.insertAt('def', 1)
console.log(lList)
// LinkedList {head: Node}
// head: Node
// data: "abc"
// next: Node
// data: "def"
// next: null
連結リストの場合は要素にアクセスするには先頭からその要素まで線形にたどるしかなくO(n)となる。いっぽうでノードの追加と削除はO(1)で済む。頻繁にデータを追加、削除するアルゴリズムでは連結リストの利用を検討。
欠点は次のノードのポインターを持たなければいけないので配列よりも多くのメモリーを必要とする。またランダムアクセスができず各ポインターを追いかけなければならない。
【アルゴリズム】JavaScriptで連結リスト問題を解く
スタック
スタックは抽象データ型であり最後に追加した要素だけを削除できる線形データ構造。ラストイン・ファーストアウト(LIFO)のデータ構造の一例。
スタックに対する要素のプッシュ・ポップはO(1)で効率的だがスタック全体にアクセスするような操作では効率的ではない。
class Stack {
constructor() {
this.items = [];
}
push(elm) {
return this.items.push(elm)
}
pop() {
if (this.items.length > 0) {
return this.items.pop()
}
}
size() {
return this.items.length
}
peek() {
return this.items[-1]
}
}
キュー
キューはファーストインファーストアウト(FIFO)で最初に入ったものが最初に出ていく。エンキューとデキューの2つの主な操作がありエンキューはキューに要素を追加する操作、デキューは要素を削除する操作。ともに計算量はO(1)。要素の参照と検索はO(n)となる。
class Queue {
constructor() {
this.items = [];
}
enqueue(elm) {
return this.items.push(elm)
}
dequeue() {
if (this.items.length > 0) {
return this.items.shift()
}
}
size() {
return this.items.length
}
peek() {
return this.items[-1]
}
}
ハッシュテーブル
連想配列の1つでキーバリューペアが格納されている線形のデータ構造でキーは一意となる。ハッシュメソッドを使用してメモリ内にデータを配置する。
2つの異なるキーから生成されるハッシュ値が同じになることを衝突とよぶ。データの探索、挿入や削除も平均でO(1)だが、衝突により効率を失ってしまうとO(n)となる。必要十分な要素のための入れ物とできる限り衝突を起こさないハッシュ関数を使用することが大事。
ハッシュテーブルは一般的に高速でランダムにデータを取り出す必要があるときに活用できるデータ構造だが、データを順番に操作するようなことがほとんどの場合は配列や連結リストのほうが良い。
let ht = new HashTable({firstname: "Mehvish", lastname: "Ashiq", age: 30});
function HashTable(person){
this.size = 0;
this.item = {};
for (let p of person) {
if (person.hasOwnProperty(p)) {
this.item[p] = person[p];
this.size++;
}
}
this.set = function(key, value){
let previousItem = undefined;
if (this.has(key)) {
previousItem = this.item[key];
}
else {
this.size++;
}
this.item[key] = value;
return previousItem;
}
this.get = function(key) {
return this.has(key) ? this.item[key] : undefined;
}
this.has = function(key){
return this.item.hasOwnProperty(key);
}
}
- 文字列内の文字の出現回数
各文字をキー、出現回数をバリューとする。O(n)の時間計算量で求められる。
const countChar = (someString) => {
const dict = {}
for(let c of someString) {
if (Object.keys(dict).some((k) => k === c)) {
dict[c] += 1
} else {
dict[c] = 1
}
}
return dict
}
console.log(countChar('abcdabcdefgh'))
// {a: 2, b: 2, c: 2, d: 2, e: 1, f: 1, g: 1, h: 1}
二分木
上記のデータ構造はすべて線形だが、木は非線形構造である。木の一番上のノードは根ノードであり、その下はすべて子ノードとなる。2つのノード間の接続は辺と呼ばれる。また子ノードを持たないノードは葉ノードと呼ばれ、子ノードを持つノードは分岐ノードと呼ばれる。二分木の場合は子ノードが2つまでという制限がある。
一般的な木や二分木のデータの挿入、削除、探索はの計算量はO(n)に対して二分探索木はO(logn)となる。これは各操作が二分探索で行われるからである。
ハッシュテーブルより優れた点としては衝突が起こらないので余分なメモリーを使わないこととデータの操作が素早くできること。
- 配列と二分探索木の比較
「2」を探すが見つからず途中で終わらない時間の処理で配列と二分探索木の比較をする。
// 二分木のノード
class BinaryTreeNode {
constructor(value) {
// そのノードの値
this.value = value;
// 左の子ノードと右の子ノード
this.left = null;
this.right = null;
}
}
// 二分探索木
class BinarySearchTree {
constructor() {
this.root = null; // 一番上のノード
}
// ノードの追加
addNode(node) {
// まだrootノードがなければそれを一番上のノードとする
if(!this.root) {
this.root = node;
return;
}
// rootノードがあれば、rootからどんどんたどっていく
// nullにあたったら終わり
let current = this.root;
let direction = node.value < current.value ? 'left' : 'right';
while(current[direction]) {
current = current[direction];
direction = node.value < current.value ? 'left' : 'right';
}
// 空いてる部分にノードを追加する
current[direction] = node;
}
}
// 100万個のデータを作って配列と二分探索木に追加する
const dataNum = 100 * 10000;
const array = [];
const tree = new BinarySearchTree();
const searchTargetValue = 2;
for(let i = 0; i < dataNum; i++) {
const value = Math.random();
array.push(value);
tree.addNode(new BinaryTreeNode(value));
}
// 配列の探索と、二分探索木の探索のステップ数をそれぞれ数える
let arraySteps = 0;
let treeSteps = 0;
// 配列
for(let i = 0; i < dataNum; i++) {
arraySteps++;
if(array[i] === searchTargetValue) {
break; // もし値が見つかったら抜ける
}
}
// 二分探索木
let current = tree.root;
while(current) {
treeSteps++;
if(current.value === searchTargetValue) {
break; // もし値が見つかったら抜ける
}
current = searchTargetValue < current.value ? current.left : current.right;
}
console.log(`配列の探索には ${arraySteps} ステップかかりました`);
console.log(`二分探索木の探索には ${treeSteps} ステップかかりました`);
// "配列の探索には 1000000 ステップかかりました"
// "二分探索木の探索には 15 ステップかかりました"
// "配列の探索には 1000000 ステップかかりました"
// "二分探索木の探索には 19 ステップかかりました"
幅優先走査
1つのデータを木から見つけるためにはすべてのノードを訪れる必要がある。レベルごとに木の各ノードを訪問することによって木のすべてのノードを訪問する幅優先走査がある。
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
insert(data) {
if (data < this.data && this.left) {
this.left.insert(data);
} else if (data < this.data) {
this.left = new Node(data);
} else if (data > this.data && this.right) {
this.right.insert(data);
} else if (data > this.data) {
this.right = new Node(data);
}
}
breadthFirstSearch(self, n) {
const current = [self]
const next = []
while(current) {
for (const node of current) {
if (node.data === n) {
return true
}
if (node.left) {
next.push(node.left)
}
if (node.right) {
next.push(node.right)
}
}
current.length = 0
current.push(...next)
next.length = 0
}
return false
}
preorder(tree) {
if (tree) {
console.log(tree.data)
this.preorder(tree.left)
this.preorder(tree.right)
}
}
}
const numberTree = new Node(2)
numberTree.insert(3)
numberTree.insert(4)
numberTree.insert(7)
numberTree.insert(8)
console.log(numberTree.breadthFirstSearch(numberTree, 7)) // true
深さ優先走査
次の兄弟ノードに移動する前にできるだけ深く一方向に進むことによってすべてのノードを訪問する。
// 行きがけ順
preorder(tree) {
if (tree) {
console.log(tree.data)
this.preorder(tree.left)
this.preorder(tree.right)
}
}