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のアルゴリズムとデータ構造

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

ウクライナ国立銀行を介してウクライナを支援する

SaveLife基金を介してウクライナを支援する

war.ukraine.uaの詳細

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

各アルゴリズムとデータ構造には、関連する説明と詳細を読むためのリンク（YouTubeビデオへのリンクを含む）を備えた独自のREADMEがあります。

他の言語でこれを読んでください： 简体中文、繁體中文、 한국어、 日本語、 Polski、 Français、 Español、 Português、 Русский、 Türk、 Italiana、 Bahasa Indonesia、 Українська、 アラビア語

☝このプロジェクトは、学習および調査の目的でのみ使用することを目的としており、本番環境での使用を目的としたものではないことに注意してください。

データ構造

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

-初心者、

-上級者

```
B
```
リンクリスト
```
B
```
二重リンクリスト
```
B
```
列
```
B
```
スタック
```
B
```
ハッシュ表
```
B
```
ヒープ-最大および最小ヒープバージョン
```
B
```
優先キュー
```
A
```
トライ
```
A
```
木
- ```
A
```
  二分探索木
- ```
A
```
  AVLツリー
- ```
A
```
  赤黒木
- ```
A
```
  セグメントツリー-最小/最大/合計範囲クエリの例
- ```
A
```
  フェニック木（バイナリインデックスツリー）
```
A
```
グラフ（有向および無向の両方）
```
A
```
素集合
```
A
```
ブルームフィルター

アルゴリズム

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

-初心者、

-上級者

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

算数
- ```
B
```
  ビット操作-ビットの設定/取得/更新/クリア、2による乗算/除算、負の値の作成など。
- ```
B
```
  BinaryFloatingPoint-浮動小数点数の2進表現。
- ```
B
```
  階乗
- ```
B
```
  フィボナッチ数-クラシックバージョンとクローズドフォームバージョン
- ```
B
```
  素因数-素因数を見つけ、ハーディ・ラマヌジャンの定理を使用してそれらを数える
- ```
B
```
  素数判定（試行割り法）
- ```
B
```
  ユークリッドの互除法-最大公約数（GCD）を計算する
- ```
B
```
  最小公倍数（LCM）
- ```
B
```
  エラトステネスのふるい-与えられた限界までのすべての素数を見つける
- ```
B
```
  2の累乗です-数値が2の累乗であるかどうかを確認します（ナイーブおよびビット単位のアルゴリズム）
- ```
B
```
  パスカルの三角形
- ```
B
```
  複素数-複素数とそれらを使用した基本的な操作
- ```
B
```
  ラジアンと度-ラジアンから度および逆方向への変換
- ```
B
```
  高速電源
- ```
B
```
  ホーナー法-多項式評価
- ```
B
```
  行列-行列と基本的な行列演算（乗算、転置など）
- ```
B
```
  ユークリッド距離-2点/ベクトル/行列間の距離
- ```
A
```
  整数パーティション
- ```
A
```
  平方根-ニュートン法
- ```
A
```
  LiuHuiπアルゴリズム-N-gonsに基づく近似π計算
- ```
A
```
  離散フーリエ変換-時間の関数（信号）をそれを構成する周波数に分解します
セット
- ```
B
```
  デカルト積-複数のセットの製品
- ```
B
```
  フィッシャー-イェーツシャッフル-有限シーケンスのランダム順列
- ```
A
```
  べき集合-セットのすべてのサブセット（ビット単位およびバックトラッキングソリューション）
- ```
A
```
  順列（繰り返しありとなし）
- ```
A
```
  組み合わせ（繰り返しありとなし）
- ```
A
```
  最長共通部分列（LCS）
- ```
A
```
  最長増加部分列
- ```
A
```
  最短共通スーパーシーケンス（SCS）
- ```
A
```
  ナップサック問題-「0/1」と「アンバウンド」の問題
- ```
A
```
  最大サブアレイ-「ブルートフォース」および「動的計画法」（カダンの）バージョン
- ```
A
```
  組み合わせの合計-特定の合計を形成するすべての組み合わせを検索します
文字列
- ```
B
```
  ハミング距離-シンボルが異なる位置の数
- ```
B
```
  回文-文字列が逆に同じかどうかを確認します
- ```
A
```
  レーベンシュタイン距離-2つのシーケンス間の最小編集距離
- ```
A
```
  Knuth–Morris–Prattアルゴリズム（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
```
  Floyd-Warshallアルゴリズム-頂点のすべてのペア間の最短経路を見つけます
- ```
A
```
  サイクルの検出-有向グラフと無向グラフの両方（DFSおよびDisjoint Setベースのバージョン）
- ```
A
```
  プリムのアルゴリズム-重み付けされた無向グラフの最小スパニングツリー（MST）を見つける
- ```
A
```
  トポロジカルソート-DFSメソッド
- ```
A
```
  アーティキュレーションポイント-タージャンのアルゴリズム（DFSベース）
- ```
A
```
  ブリッジ-DFSベースのアルゴリズム
- ```
A
```
  オイラーパスとオイラー回路-フルーリーのアルゴリズム-すべてのエッジを1回だけ訪問する
- ```
A
```
  ハミルトン閉路-すべての頂点に1回だけアクセスする
- ```
A
```
  強連結成分-コサラジュのアルゴリズム
- ```
A
```
  巡回セールスマン問題-各都市を訪れ、元の都市に戻る最短ルート
暗号化
- ```
B
```
  多項式ハッシュ-多項式に基づくローリングハッシュ関数
- ```
B
```
  RailFenceCipher-メッセージをエンコードするための転置暗号アルゴリズム
- ```
B
```
  シーザー暗号-単純な換字式暗号
- ```
B
```
  ヒル暗号-線形代数に基づく換字式暗号
機械学習
- ```
B
```
  NanoNeuron-マシンが実際に学習する方法を示す7つの単純なJS関数（順方向/逆方向の伝播）
- ```
B
```
  k-NN -k最近傍分類アルゴリズム
- ```
B
```
  k-Means -k-Meansクラスタリングアルゴリズム
画像処理
- ```
B
```
  シームカービング-コンテンツ対応の画像サイズ変更アルゴリズム
統計学
- ```
B
```
  加重ランダム-アイテムの加重に基づいてリストからランダムなアイテムを選択します
進化的アルゴリズム
- ```
A
```
  遺伝的アルゴリズム-セルフパーキングカーのトレーニングに遺伝的アルゴリズムを適用する方法の例
未分類
- ```
B
```
  ハノイの塔
- ```
B
```
  正方行列回転-インプレースアルゴリズム
- ```
B
```
  ジャンプゲーム-バックトラック、動的計画法（トップダウン+ボトムアップ）および貪欲な例
- ```
B
```
  ユニークなパス-バックトラッキング、動的計画法、パスカルの三角形ベースの例
- ```
B
```
  レインテラス-雨水のトラップの問題（動的計画法とブルートフォースバージョン）
- ```
B
```
  再帰的階段-トップに到達する方法の数を数えます（4つのソリューション）
- ```
B
```
  株を売るのに最適な時期-分割統治法とワンパスの例
- ```
A
```
  N-クイーンズの問題
- ```
A
```
  ナイトツアー

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

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

ブルートフォース-すべての可能性を検討し、最適なソリューションを選択します
- ```
B
```
  線形探索
- ```
B
```
  レインテラス-雨水のトラップの問題
- ```
B
```
  再帰階段-一番上に到達する方法の数を数えます
- ```
A
```
  最大サブアレイ
- ```
A
```
  巡回セールスマン問題-各都市を訪れ、元の都市に戻る最短ルート
- ```
A
```
  離散フーリエ変換-時間の関数（信号）をそれを構成する周波数に分解します
貪欲-将来を考慮せずに、現時点で最良のオプションを選択してください
- ```
B
```
  ジャンプゲーム
- ```
A
```
  アンバウンドナップサック問題
- ```
A
```
  ダイクストラアルゴリズム-すべてのグラフ頂点への最短経路を見つける
- ```
A
```
  プリムのアルゴリズム-重み付けされた無向グラフの最小スパニングツリー（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
```
  Floyd-Warshallアルゴリズム-頂点のすべてのペア間の最短経路を見つけます
- ```
A
```
  正規表現マッチング
バックトラック-ブルートフォースと同様に、考えられるすべてのソリューションを生成しようとしますが、次のソリューションを生成するたびに、それがすべての条件を満たすかどうかをテストし、その後、後続のソリューションの生成を続行します。それ以外の場合は、バックトラックして、解決策を見つけるための別のパスに進みます。通常、状態空間のDFSトラバーサルが使用されています。
- ```
B
```
  ジャンプゲーム
- ```
B
```
  ユニークなパス
- ```
B
```
  べき集合-セットのすべてのサブセット
- ```
A
```
  ハミルトン閉路-すべての頂点に1回だけアクセスする
- ```
A
```
  N-クイーンズの問題
- ```
A
```
  ナイトツアー
- ```
A
```
  組み合わせの合計-特定の合計を形成するすべての組み合わせを検索します
Branch＆Bound-バックトラッキング検索の各段階で見つかった最低コストのソリューションを覚えて、問題の最小コストのソリューションのコストの下限として、これまでに見つかった最低コストのソリューションのコストを使用します。これまでに見つかった最低コストのソリューションよりもコストが高い部分的なソリューションを破棄するため。通常、状態空間ツリーのDFSトラバーサルと組み合わせたBFSトラバーサルが使用されています。

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

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

npm install

ESLintを実行する

コードの品質をチェックするために実行することをお勧めします。

npm run lint

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

npm test

名前でテストを実行する

npm test -- 'LinkedList'

トラブルシューティング

リンティングまたはテストが失敗した場合は、

node_modules

フォルダーを削除してnpmパッケージを再インストールしてみてください。

rm -rf ./node_modules
npm i

また、正しいノードバージョン（

>=14.16.0

）を使用していることを確認してください。ノードバージョン管理にnvmを使用している場合

nvm use

は、プロジェクトのルートフォルダーから実行すると、正しいバージョンが取得されます。

遊び場

ファイル内のデータ構造とアルゴリズムで遊んで、で

./src/playground/playground.js

テストを書くことができます

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

。

次に、次のコマンドを実行して、プレイグラウンドコードが期待どおりに機能するかどうかをテストします。

npm test -- 'playground'

有用な情報

参考文献

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

ビッグO表記

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

出典：BigOチートシート。

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

ビッグO表記	タイプ	10要素の計算	100要素の計算	1000要素の計算
O（1）	絶え間ない	1	1	1
O（log N）	対数	3	6	9
オン）	線形	10	100	1000
O（N log N）	n log（n）	30	600	9000
O（N ^ 2）	二次方程式	100	10000	1000000
O（2 ^ N）	指数関数	1024	1.26e + 29	1.07e + 301
オン！）	階乗	3628800	9.3e + 157	4.02e + 2567

データ構造操作の複雑さ

データ構造	アクセス	探す	挿入	消す	コメントコメント
配列	1	n	n	n
スタック	n	n	1	1
列	n	n	1	1
リンクリスト	n	n	1	n
ハッシュ表	-	n	n	n	完全なハッシュ関数の場合、コストはO（1）になります。
二分探索木	n	n	n	n	バランスの取れたツリーの場合、コストはO（log（n））になります。
Bツリー	log（n）	log（n）	log（n）	log（n）
赤黒木	log（n）	log（n）	log（n）	log（n）
AVLツリー	log（n）	log（n）	log（n）	log（n）
ブルームフィルター	-	1	1	-	検索中に誤検知が発生する可能性があります

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

名前	一番	平均	最悪	メモリー	安定	コメントコメント
バブルソート	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 ²	log（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とアルゴリズムに関するいくつかのプロジェクトと記事