Permalink
Branch: master
Find file Copy path
d885fd2 Dec 11, 2018
2 contributors

Users who have contributed to this file

@trekhleb @Minki-Kim95
292 lines (252 sloc) 22.2 KB

JavaScriptアルゴリズムとデータ構造

Build Status codecov

このリポジトリには、JavaScriptベースの多数のサンプル 一般的なアルゴリズムとデータ構造。

各アルゴリズムとデータ構造には独自のREADMEがあります 関連する説明と、さらに読むためのリンク (関連YouTubeのビデオも含まれてい).

Read this in other languages: English, 简体中文, 繁體中文, 한국어, Polski, Français, Español, Português

データ構造

データ構造は、データ値、データ値との間の関係、 そして、データを扱うことができる関数と演算の集合で、 データを特定の方法で構成して保存することで、より効率的に アクセスして変更することができます。

B - 初心者, A - 上級

アルゴリズム

アルゴリズムとは、問題のクラスをどのように解決するかの明確な仕様です。 一連の操作を正確に定義する一連のルールです。

B - 初心者, A - 上級

トピック別アルゴリズム

Paradigmによるアルゴリズム

アルゴリズムパラダイムは、あるクラスのアルゴリズムの設計の基礎をなす一般的な方法またはアプローチである。それは、アルゴリズムがコンピュータプログラムよりも高い抽象であるのと同様に、アルゴリズムの概念よりも高い抽象である。

このリポジトリの使い方

すべての依存関係をインストールする

npm install

ESLintを実行する

これを実行してコードの品質をチェックすることができます。

npm run lint

すべてのテストを実行する

npm test

名前でテストを実行する

npm test -- 'LinkedList'

playground

データ構造とアルゴリズムを ./src/playground/playground.js ファイルで再生し、 それに対するテストを書くことができ ./src/playground/__test__/playground.test.js.

次に、次のコマンドを実行して、遊び場コードが正常に動作するかどうかをテストします。

npm test -- 'playground'

有用な情報

参考文献

▶ データ構造とアルゴリズム on YouTube

ビッグO表記

Big O表記法は 入力サイズが大きくなるにつれて実行時間やスペース要件がどのように増加するかに応じてアルゴリズムを分類するために使用されます。下のチャートでは、Big O表記で指定されたアルゴリズムの成長の最も一般的な順序を見つけることができます。

Big Oグラフ

出典: Big Oチートシート.

以下は、最も使用されているBig O表記のリストと、入力データのさまざまなサイズに対するパフォーマンス比較です。

Big O Notation Computations for 10 elements Computations for 100 elements Computations for 1000 elements
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 600 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1.26e+29 1.07e+301
O(N!) 3628800 9.3e+157 4.02e+2567

データ構造操作の複雑さ

Data Structure Access Search Insertion Deletion Comments
Array 1 n n n
Stack n n 1 1
Queue n n 1 1
Linked List n n 1 1
Hash Table - n n n In case of perfect hash function costs would be O(1)
Binary Search Tree n n n n In case of balanced tree costs would be O(log(n))
B-Tree log(n) log(n) log(n) log(n)
Red-Black Tree log(n) log(n) log(n) log(n)
AVL Tree log(n) log(n) log(n) log(n)
Bloom Filter - 1 1 - False positives are possible while searching

配列の並べ替えアルゴリズムの複雑さ

Name Best Average Worst Memory Stable Comments
Bubble sort n n2 n2 1 Yes
Insertion sort n n2 n2 1 Yes
Selection sort n2 n2 n2 1 No
Heap sort n log(n) n log(n) n log(n) 1 No
Merge sort n log(n) n log(n) n log(n) n Yes
Quick sort n log(n) n log(n) n2 log(n) No Quicksort is usually done in-place with O(log(n)) stack space
Shell sort n log(n) depends on gap sequence n (log(n))2 1 No
Counting sort n + r n + r n + r n + r Yes r - biggest number in array
Radix sort n * k n * k n * k n + k Yes k - length of longest key