README.ja-JP.md
このリポジトリには、JavaScriptベースの一般的なアルゴリズムとデータ構造に関する多数のサンプルが含まれています。
各アルゴリズムとデータ構造には独自のREADMEがあります。 関連する説明、そして参考資料 (YouTube動画)も含まれています。
Read this in other languages: English, 简体中文, 繁體中文, 한국어, Polski, Français, Español, Português, Русский, Türk, Italiana, Bahasa Indonesia, Українська, Arabic, Tiếng Việt, Deutsch, Uzbek עברית
データ構造は、データ値、データ値との間の関係、 そして、データを扱うことができる関数と演算の集合で、 データを特定の方法で構成して保存することで、より効率的に アクセスして変更することができます。
B - 初心者, A - 上級
B リンクされたリストB 二重リンクリストB キューB スタックB ハッシュ表B ヒープ - max and min heap versionsB 優先度キューA トライA ツリー
A バイナリ検索ツリーA AVLツリーA 赤黒のツリーA セグメントツリー - with min/max/sum range queries examplesA フェンウィック・ツリー (Binary Indexed Tree)A グラフ (both directed and undirected)A 分離集合A ブルームフィルタアルゴリズムとは、問題のクラスをどのように解決するかの明確な仕様です。 一連の操作を正確に定義する一連のルールです。
B - 初心者, A - 上級
B ビット操作 - set/get/update/clear bits, 2つの乗算/除算, 否定的にする. 等B 因果関係B フィボナッチ数 - クラシックとクローズドフォームのバージョンB 素数性テスト (trial division 方法)B ユークリッドアルゴリズム - 最大公約数を計算する (GCD)B 最小公倍数 (LCM)B エラトステネスのふるい - 与えられた限度まですべての素数を見つけるB Is Power of Two - 数値が2の累乗であるかどうかを調べる（単純なアルゴリズムとビットごとのアルゴリズム）B パスカルの三角形B 複素数 - 複素数とその基本演算B ラジアン＆度 - 度数と逆方向の変換に対するラジアンB 高速電力供給A 整数パーティションA Liu Hui π アルゴリズム - N-gonsに基づく近似π計算A 離散フーリエ変換 - 時間（信号）の関数をそれを構成する周波数に分解するB デカルト積 - 複数の積の積B Fisher–Yates Shuffle - 有限シーケンスのランダム置換A パワーセット - セットのすべてのサブセット（ビットごとのソリューションとバックトラッキングソリューション）A 順列 （繰り返しの有無にかかわらず）A 組み合わせ （繰返しあり、繰返しなし）A 最長共通部分列 (LCS)A 最長増加サブシーケンスA 最短共通スーパーシーケンス (SCS)A ナップザック問題 - 「0/1」と「非結合」問題A 最大サブアレイ - 「ブルートフォース」と「ダイナミックプログラミング」（Kadane's版）A 組み合わせ合計 - 特定の合計を構成するすべての組み合わせを見つけるB ハミング距離 - シンボルが異なる位置の数A レーベンシュタイン距離 - 2つのシーケンス間の最小編集距離A Knuth-Morris-Prattアルゴリズム (KMP Algorithm) - 部分文字列検索 (pattern matching)A Z アルゴリズム - 部分文字列検索 (pattern matching)A Rabin Karpアルゴリズム - 部分文字列検索A 最長共通部分文字列A 正規表現マッチングB 深度優先検索 (DFS)B 幅優先検索 (BFS)B Kruskalのアルゴリズム - 重み付き無向グラフの最小スパニングツリー（MST）の発見A Dijkstraアルゴリズム - 単一の頂点からすべてのグラフ頂点への最短経路を見つけるA Bellman-Fordアルゴリズム - 単一の頂点からすべてのグラフ頂点への最短経路を見つけるA Floyd-Warshallアルゴリズム - すべての頂点ペア間の最短経路を見つけるA Detect Cycle - 有向グラフと無向グラフの両方（DFSおよびディスジョイントセットベースのバージョン）A プリムのアルゴリズム - 重み付き無向グラフの最小スパニングツリー（MST）の発見A トポロジカルソート - DFSメソッドA アーティキュレーションポイント - Tarjanのアルゴリズム（DFSベース）A ブリッジ - DFSベースのアルゴリズムA オイラーパスとオイラー回路 - フルリーアルゴリズム - すべてのエッジを正確に1回訪問するA ハミルトニアンサイクル - すべての頂点を正確に1回訪問するA 強連結成分 - コサラジュのアルゴリズムA トラベリングセールスマン問題 - 各都市を訪問し、起点都市に戻る最短経路B 多項式ハッシュ - 関数多項式に基づくハッシュ関数アルゴリズムパラダイムは、あるクラスのアルゴリズムの設計の基礎をなす一般的な方法またはアプローチである。それは、アルゴリズムがコンピュータプログラムよりも高い抽象であるのと同様に、アルゴリズムの概念よりも高い抽象である。
B 線形探索B レインテラス - 雨水問題B Recursive Staircase - 先頭に到達する方法の数を数えますA 最大サブアレイA 旅行セールスマン問題 - 各都市を訪れ、起点都市に戻る最短ルートA 離散フーリエ変換 - 時間（信号）の関数をそれを構成する周波数に分解するB ジャンプゲームA 結合されていないナップザック問題A Dijkstra Algorithm - すべてのグラフ頂点への最短経路を見つけるA Prim’s Algorithm - 重み付き無向グラフの最小スパニングツリー（MST）を見つけるA Kruskalのアルゴリズム - 重み付き無向グラフの最小スパニングツリー（MST）を見つけるB バイナリ検索B ハノイの塔B パスカルの三角形B ユークリッドアルゴリズム - GCD（Greatest Common Divisor）を計算するB マージソートB クイックソートB ツリーの深さ優先検索 (DFS)B グラフの深さ優先検索 (DFS)B ジャンプゲームB 高速電力供給A 順列 （繰り返しの有無にかかわらず）A 組み合わせ（繰返しあり、繰返しなし）B フィボナッチ数B ジャンプゲームB ユニークなパスB 雨テラス - トラップ雨水問題B 再帰的階段 - 上に到達する方法の数を数えるA Levenshtein Distance - 2つのシーケンス間の最小編集距離A 最長共通部分列 (LCS)A 最長共通部分文字列A 最長増加サブシーケンスA 最短共通共通配列A 0/1ナップザック問題A 整数パーティションA 最大サブアレイA Bellman-Fordアルゴリズム - すべてのグラフ頂点への最短経路を見つけるA Floyd-Warshallアルゴリズム - すべての頂点ペア間の最短経路を見つけるA 正規表現マッチングすべての依存関係をインストールする
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'
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 | n<sup>2</sup> | n<sup>2</sup> | 1 | Yes | |
| Insertion sort | n | n<sup>2</sup> | n<sup>2</sup> | 1 | Yes | |
| Selection sort | n<sup>2</sup> | n<sup>2</sup> | n<sup>2</sup> | 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) | n<sup>2</sup> | 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))<sup>2</sup> | 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 |
ℹ️ A few more projects and articles about JavaScript and algorithms on trekhleb.dev