javascript-algorithms - 📝 JavaScript で実装されたアルゴリズムとデータ構造、および説明とさらなる読み物へのリンク

(📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings)

Created at: 2018-03-24 15:47:04

Language: JavaScript

URL: https://github.com/trekhleb/javascript-algorithms

License: MIT

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

🇺🇦ウクライナはロシア軍に攻撃されています。民間人が殺されています。住宅地は爆撃を受けています。

ウクライナ国立銀行経由でウクライナを支援する

セーブライフ基金を通じてウクライナを支援する

ウクライナの war.ukraine.ua とMFAに関する詳細情報

このリポジトリには、JavaScript ベースの多くの例が含まれています。一般的なアルゴリズムとデータ構造。

各アルゴリズムとデータ構造には、独自の個別の README があります。関連する説明とさらに読むためのリンク(ものを含む) ユーチューブの動画に)。

他の言語でこれを読んでください: 简体中文, 繁體中文, 한국어, 日本語, ポルスキ, フランス語, スペイン語, ポルトガル語, Русский, テュルクチェ語, イタリア語, インドネシア語, Українська, アラビア語, ティエン・ヴィエット, ドイツ語

☝ このプロジェクトは、学習および研究目的で使用されることを意図していることに注意してくださいのみであり、生産に使用することを意図したものではありません。

データ構造

データ構造は、コンピューターにデータを整理して保存する特定の方法です。効率的にアクセスして変更します。より正確には、データ構造はデータのコレクションです値、それらの間の関係、および適用できる関数または操作データ。

- 初心者、 - 上級者

```
B
```
リンクリスト
```
B
```
二重リンクリスト
```
B
```
列
```
B
```
スタック
```
B
```
ハッシュテーブル
```
B
```
ヒープ - 最大ヒープバージョンと最小ヒープバージョン
```
B
```
プライオリティキュー
```
A
```
トライ
```
A
```
木
- ```
A
```
  バイナリ検索ツリー
- ```
A
```
  AVL ツリー
- ```
A
```
  赤黒の木
- ```
A
```
  セグメントツリー - 最小/最大/合計範囲クエリの例
- ```
A
```
  フェンウィックツリー(バイナリインデックスツリー)
```
A
```
グラフ (有向と無向の両方)
```
A
```
不整合セット
```
A
```
ブルームフィルター

アルゴリズム

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

- 初心者、 - 上級者

トピック別のアルゴリズム

数学
- ```
B
```
  ビット操作 - ビットの設定/取得/更新/クリア、2による乗算/除算、負にするなど
- ```
B
```
  バイナリ浮動小数点 - 浮動小数点数のバイナリ表現。
- ```
B
```
  階乗
- ```
B
```
  フィボナッチ数 - クラシックバージョンとクローズドフォームバージョン
- ```
B
```
  素因数 - 素因数を見つけ、ハーディ・ラマヌジャンの定理を使用してそれらを数えます
- ```
B
```
  素数性検定(試行分割法)
- ```
B
```
  ユークリッドアルゴリズム - 最大公約数(GCD)を計算する
- ```
B
```
  最小公倍数 (LCM)
- ```
B
```
  エラトステネスのふるい - 与えられた限界までのすべての素数を見つける
- ```
B
```
  2の累乗 - 数値が2の累乗であるかどうかを確認します(ナイーブアルゴリズムとビット単位のアルゴリズム)
- ```
B
```
  パスカルの三角形
- ```
B
```
  複素数 - 複素数とそれらを使った基本的な操作
- ```
B
```
  Radian & Degree - ラジアンから度および逆方向への変換
- ```
B
```
  高速電力
- ```
B
```
  ホーナー法 - 多項式評価
- ```
B
```
  行列 - 行列と基本的な行列演算(乗算、転置など)
- ```
B
```
  ユークリッド距離 - 2点/ベクトル/行列間の距離
- ```
A
```
  整数パーティション
- ```
A
```
  平方根 - ニュートンの方法
- ```
A
```
  劉慧πアルゴリズム - N角形に基づく近似π計算
- ```
A
```
  離散フーリエ変換 - 時間の関数(信号)をそれを構成する周波数に分解します
設定
- ```
B
```
  デカルト積 - 複数集合の積
- ```
B
```
  フィッシャー・イェーツ・シャッフル - 有限列のランダム順列
- ```
A
```
  パワーセット - セットのすべてのサブセット(ビット単位およびバックトラッキングソリューション)
- ```
A
```
  順列(繰り返しありと繰り返しなし)
- ```
A
```
  組み合わせ(繰り返しありと繰り返しなし)
- ```
A
```
  最長共通部分列 (LCS)
- ```
A
```
  最長増加部分列
- ```
A
```
  最短共通スーパーシーケンス (SCS)
- ```
A
```
  ナップザック問題-「0/1」と「バインド解除」の問題
- ```
A
```
  最大サブアレイ - "ブルートフォース" および "動的計画法" (Kadane's) バージョン
- ```
A
```
  組み合わせ合計 - 特定の合計を形成するすべての組み合わせを検索します
ストリングス
- ```
B
```
  ハミング距離 - シンボルが異なる位置の数
- ```
B
```
  回文-文字列が逆に同じかどうかを確認します
- ```
A
```
  レーベンシュタイン距離 - 2つのシーケンス間の最小編集距離
- ```
A
```
  クヌース・モリス・プラットアルゴリズム (KMP アルゴリズム) - 部分文字列検索 (パターンマッチング)
- ```
A
```
  Z アルゴリズム - 部分文字列検索 (パターンマッチング)
- ```
A
```
  ラビンカープアルゴリズム - 部分文字列検索
- ```
A
```
  最長共通部分文字列
- ```
A
```
  正規表現マッチング
検索
- ```
B
```
  線形探索
- ```
B
```
  ジャンプ検索(またはブロック検索) - ソートされた配列で検索
- ```
B
```
  バイナリ検索 - ソートされた配列で検索
- ```
B
```
  補間検索 - 一様に分布したソート配列で検索
分別
- ```
B
```
  バブルソート
- ```
B
```
  選択ソート
- ```
B
```
  挿入ソート
- ```
B
```
  ヒープソート
- ```
B
```
  マージソート
- ```
B
```
  クイックソート - インプレース実装とノンインプレース実装
- ```
B
```
  シェルソート
- ```
B
```
  カウントソート
- ```
B
```
  基数ソート
リンクリスト
- ```
B
```
  ストレートトラバーサル
- ```
B
```
  逆トラバーサル
樹木
- ```
B
```
  深さ優先検索 (DFS)
- ```
B
```
  幅優先検索 (BFS)
グラフ
- ```
B
```
  深さ優先検索 (DFS)
- ```
B
```
  幅優先検索 (BFS)
- ```
B
```
  クラスカルのアルゴリズム - 重み付き無向グラフの最小スパニングツリー(MST)の検索
- ```
A
```
  ダイクストラアルゴリズム - 単一の頂点からすべてのグラフ頂点への最短経路を見つける
- ```
A
```
  ベルマン・フォードアルゴリズム - 単一の頂点からすべてのグラフ頂点への最短経路を見つける
- ```
A
```
  フロイド・ワーシャルアルゴリズム - 頂点のすべてのペア間の最短経路を見つける
- ```
A
```
  サイクルの検出 - 有向グラフと無向グラフの両方(DFSおよび不整合集合ベースのバージョン)
- ```
A
```
  Primのアルゴリズム - 重み付き無向グラフの最小スパニングツリー(MST)の検索
- ```
A
```
  トポロジカルソーティング - DFS法
- ```
A
```
  アーティキュレーションポイント - タージャンのアルゴリズム(DFSベース)
- ```
A
```
  ブリッジ - DFS ベースのアルゴリズム
- ```
A
```
  オイラー経路とオイラー回路 - フルーリーのアルゴリズム - すべてのエッジを一度だけ訪問する
- ```
A
```
  ハミルトニアンサイクル - すべての頂点に一度だけアクセス
- ```
A
```
  強く接続されたコンポーネント - コサラジュのアルゴリズム
- ```
A
```
  巡回セールスマン問題 - 各都市を訪れ、出発都市に戻る最短ルート
暗号化手法
- ```
B
```
  多項式ハッシュ - 多項式に基づくローリングハッシュ関数
- ```
B
```
  レールフェンス暗号 - メッセージをエンコードするための転置暗号アルゴリズム
- ```
B
```
  シーザー暗号 - 単純な置換暗号
- ```
B
```
  ヒル暗号 - 線形代数に基づく置換暗号
機械学習
- ```
B
```
  NanoNeuron - 機械が実際に学習する方法を示す7つの単純なJS関数(順方向/逆方向伝播)
- ```
B
```
  k-NN - k 最近傍分類アルゴリズム
- ```
B
```
  K- 平均法のクラスタリングアルゴリズム
画像処理
- ```
B
```
  シームカービング - コンテンツ対応の画像サイズ変更アルゴリズム
統計学
- ```
B
```
  加重ランダム - アイテムの重みに基づいてリストからランダムなアイテムを選択します
進化的アルゴリズム
- ```
A
```
  遺伝的アルゴリズム - 遺伝的アルゴリズムを自走車のトレーニングにどのように適用できるかの例
未分類
- ```
B
```
  ハノイの塔
- ```
B
```
  正方行列回転 - インプレースアルゴリズム
- ```
B
```
  ジャンプゲーム-バックトラッキング、動的プログラミング(トップダウン+ボトムアップ)、および貪欲な例
- ```
B
```
  ユニークパス - バックトラッキング、動的計画法、パスカルの三角形ベースの例
- ```
B
```
  レインテラス - 雨水問題のトラップ(動的プログラミングとブルートフォースバージョン)
- ```
B
```
  再帰的階段 - 頂上に到達する方法の数を数える(4つの解決策)
- ```
B
```
  株を売って購入するのに最適な時期-分割統治とワンパスの例
- ```
A
```
  Nクイーンズ問題
- ```
A
```
  騎士のツアー

パラダイムによるアルゴリズム

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

ブルートフォース-すべての可能性を見て、最適なソリューションを選択します
- ```
B
```
  線形探索
- ```
B
```
  レインテラス - 雨水問題のトラップ
- ```
B
```
  再帰的階段 - 頂上に到達する方法の数を数えます
- ```
A
```
  最大サブアレイ
- ```
A
```
  巡回セールスマン問題 - 各都市を訪れ、出発都市に戻る最短ルート
- ```
A
```
  離散フーリエ変換 - 時間の関数(信号)をそれを構成する周波数に分解します
貪欲-将来を考慮せずに、現時点で最適なオプションを選択します
- ```
B
```
  ジャンプゲーム
- ```
A
```
  アンバウンドナップザック問題
- ```
A
```
  ダイクストラアルゴリズム - すべてのグラフ頂点への最短経路を見つける
- ```
A
```
  Primのアルゴリズム - 重み付き無向グラフの最小スパニングツリー(MST)の検索
- ```
A
```
  クラスカルのアルゴリズム - 重み付き無向グラフの最小スパニングツリー(MST)の検索
分割統治 - 問題を小さな部分に分割し、それらの部分を解決します
- ```
B
```
  バイナリ検索
- ```
B
```
  ハノイの塔
- ```
B
```
  パスカルの三角形
- ```
B
```
  ユークリッドアルゴリズム - 最大公約数(GCD)を計算する
- ```
B
```
  マージソート
- ```
B
```
  クイックソート
- ```
B
```
  ツリーの深さ優先検索 (DFS)
- ```
B
```
  グラフの深さ優先検索 (DFS)
- ```
B
```
  行列 - さまざまな形状の行列を生成してトラバース
- ```
B
```
  ジャンプゲーム
- ```
B
```
  高速電力
- ```
B
```
  株を売って購入するのに最適な時期-分割統治とワンパスの例
- ```
A
```
  順列(繰り返しありと繰り返しなし)
- ```
A
```
  組み合わせ(繰り返しありと繰り返しなし)
- ```
A
```
  最大サブアレイ
動的計画法 - 以前に見つかったサブソリューションを使用してソリューションを構築する
- ```
B
```
  フィボナッチ数
- ```
B
```
  ジャンプゲーム
- ```
B
```
  一意のパス
- ```
B
```
  レインテラス - 雨水問題のトラップ
- ```
B
```
  再帰的階段 - 頂上に到達する方法の数を数えます
- ```
B
```
  シームカービング - コンテンツ対応の画像サイズ変更アルゴリズム
- ```
A
```
  レーベンシュタイン距離 - 2つのシーケンス間の最小編集距離
- ```
A
```
  最長共通部分列 (LCS)
- ```
A
```
  最長共通部分文字列
- ```
A
```
  最長増加部分列
- ```
A
```
  最短共通スーパーシーケンス
- ```
A
```
  0/1ナップザック問題
- ```
A
```
  整数パーティション
- ```
A
```
  最大サブアレイ
- ```
A
```
  ベルマン・フォードアルゴリズム - すべてのグラフ頂点への最短経路を見つける
- ```
A
```
  フロイド・ワーシャルアルゴリズム - 頂点のすべてのペア間の最短経路を見つける
- ```
A
```
  正規表現マッチング
バックトラッキング - ブルートフォースと同様に、考えられるすべてのソリューションを生成しようとしますが、次のソリューションを生成するたびにテストしますそれがすべての条件を満たす場合、その後の解を生成し続けます。それ以外の場合は、後戻りして、解決策を見つけるための異なるパス。通常、状態空間の DFS トラバーサルが使用されています。
- ```
B
```
  ジャンプゲーム
- ```
B
```
  一意のパス
- ```
B
```
  パワーセット - セットのすべてのサブセット
- ```
A
```
  ハミルトニアンサイクル - すべての頂点に一度だけアクセス
- ```
A
```
  Nクイーンズ問題
- ```
A
```
  騎士のツアー
- ```
A
```
  組み合わせ合計 - 特定の合計を形成するすべての組み合わせを検索します
Branch & Bound - バックトラックの各段階で見つかった最も低コストのソリューションを記憶する検索し、これまでに見つかった最も低コストのソリューションのコストをコストの下限として使用します問題に対する最小コストの解決策は、これまでに見つかった最も低コストのソリューション。通常、状態空間のDFSトラバーサルと組み合わせたBFSトラバーサルツリーが使用されています。

このリポジトリの使用方法

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

npm install

ESLint を実行する

コードの品質を確認するために実行することをお勧めします。

npm run lint

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

npm test

Run tests by name

npm test -- 'LinkedList'

Troubleshooting

If linting or testing is failing, try to delete the folder and re-install npm packages:

node_modules

rm -rf ./node_modules
npm i

Also make sure that you're using a correct Node version (). If you're using nvm for Node version management you may run from the root folder of the project and the correct version will be picked up.

>=14.16.0

nvm use

Playground

You may play with data-structures and algorithms in file and write tests for it in .

./src/playground/playground.js

./src/playground/__test__/playground.test.js

Then just simply run the following command to test if your playground code works as expected:

npm test -- 'playground'

Useful Information

References

Big O Notation

Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. On the chart below you may find most common orders of growth of algorithms specified in Big O notation.

Source: Big O Cheat Sheet.

Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.

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

Data Structure Operations Complexity

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	n
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

配列ソートアルゴリズムの複雑さ

名前	最良	平均	ワースト	記憶	厩	コメント
バブルソート	n	n²	n²	1	はい
挿入ソート	n	n²	n²	1	はい
選択ソート	n²	n²	n²	1	いいえ
ヒープソート	n log(n)	n log(n)	n log(n)	1	いいえ
マージソート	n log(n)	n log(n)	n log(n)	n	はい
クイックソート	n log(n)	n log(n)	n²	ログ(n)	いいえ	クイックソートは通常、O(log(n))スタックスペースを使用してインプレースで行われます
シェルソート	n log(n)	ギャップシーケンスに依存	n (log(n))²	1	いいえ
カウントソート	n + r	n + r	n + r	n + r	はい	r - 配列内の最大数
基数ソート	n * k	n * k	n * k	n + k	はい	k - 最長キーの長さ

プロジェクト支援者

このプロジェクトは、️ GitHub または ❤️️ Patreon を介して❤️サポートできます。

このプロジェクトを支えている人々

∑ = 0

ℹ️trekhleb.dev に関するJavaScriptとアルゴリズムに関するいくつかのプロジェクトと記事

著者

@trekhleb