🇺🇦 ウクライナはロシア軍に攻撃されています。民間人が殺されています。住宅地は爆撃を受けています。
- ウクライナ国立銀行経由でウクライナを支援する
- セーブライフ基金を通じてウクライナを支援する
- ウクライナの war.ukraine.ua とMFAに関する詳細情報
このリポジトリには、JavaScript ベースの多くの例が含まれています。 一般的なアルゴリズムとデータ構造。
各アルゴリズムとデータ構造には、独自の個別の README があります。 関連する説明とさらに読むためのリンク(ものを含む) ユーチューブの動画に)。
他の言語でこれを読んでください: 简体中文, 繁體中文, 한국어, 日本語, ポルスキ, フランス語, スペイン語, ポルトガル語, Русский, テュルクチェ語, イタリア語, インドネシア語, Українська, アラビア語, ティエン・ヴィエット, ドイツ語
データ構造は、コンピューターにデータを整理して保存する特定の方法です。 効率的にアクセスして変更します。より正確には、データ構造はデータのコレクションです 値、それらの間の関係、および適用できる関数または操作 データ。
B- 初心者、 - 上級者
A
Bリンクリスト
B二重リンクリスト
B列
Bスタック
Bハッシュ テーブル
Bヒープ - 最大ヒープ バージョンと最小ヒープ バージョン
Bプライオリティ キュー
Aトライ
A木
Aバイナリ検索ツリー
AAVL ツリー
A赤黒の木
Aセグメントツリー - 最小/最大/合計範囲クエリの例
Aフェンウィックツリー(バイナリインデックスツリー)
Aグラフ (有向と無向の両方)
A不整合セット
Aブルームフィルター
アルゴリズムは、問題のクラスを解決する方法の明確な仕様です。そうです 一連の操作を正確に定義する一連のルール。
B- 初心者、 - 上級者
A
Bビット操作 - ビットの設定/取得/更新/クリア、2による乗算/除算、負にするなど
Bバイナリ浮動小数点 - 浮動小数点数のバイナリ表現。
B階乗
Bフィボナッチ数 - クラシックバージョンとクローズドフォームバージョン
B素因数 - 素因数を見つけ、ハーディ・ラマヌジャンの定理を使用してそれらを数えます
B素数性検定(試行分割法)
Bユークリッドアルゴリズム - 最大公約数(GCD)を計算する
B最小公倍数 (LCM)
Bエラトステネスのふるい - 与えられた限界までのすべての素数を見つける
B2の累乗 - 数値が2の累乗であるかどうかを確認します(ナイーブアルゴリズムとビット単位のアルゴリズム)
Bパスカルの三角形
B複素数 - 複素数とそれらを使った基本的な操作
BRadian & 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 アルゴリズム) - 部分文字列検索 (パターンマッチング)
AZ アルゴリズム - 部分文字列検索 (パターン マッチング)
Aラビンカープアルゴリズム - 部分文字列検索
A最長共通部分文字列
A正規表現マッチング
Bストレートトラバーサル
B逆トラバーサル
B深さ優先検索 (DFS)
B幅優先検索 (BFS)
Bクラスカルのアルゴリズム - 重み付き無向グラフの最小スパニングツリー(MST)の検索
Aダイクストラアルゴリズム - 単一の頂点からすべてのグラフ頂点への最短経路を見つける
Aベルマン・フォードアルゴリズム - 単一の頂点からすべてのグラフ頂点への最短経路を見つける
Aフロイド・ワーシャルアルゴリズム - 頂点のすべてのペア間の最短経路を見つける
Aサイクルの検出 - 有向グラフと無向グラフの両方(DFSおよび不整合集合ベースのバージョン)
APrimのアルゴリズム - 重み付き無向グラフの最小スパニングツリー(MST)の検索
Aトポロジカルソーティング - DFS法
Aアーティキュレーションポイント - タージャンのアルゴリズム(DFSベース)
Aブリッジ - DFS ベースのアルゴリズム
Aオイラー経路とオイラー回路 - フルーリーのアルゴリズム - すべてのエッジを一度だけ訪問する
Aハミルトニアンサイクル - すべての頂点に一度だけアクセス
A強く接続されたコンポーネント - コサラジュのアルゴリズム
A巡回セールスマン問題 - 各都市を訪れ、出発都市に戻る最短ルート
BNanoNeuron - 機械が実際に学習する方法を示す7つの単純なJS関数(順方向/逆方向伝播)
Bk-NN - k 最近傍分類アルゴリズム
BK- 平均法のクラスタリング アルゴリズム
Bシームカービング - コンテンツ対応の画像サイズ変更アルゴリズム
B加重ランダム - アイテムの重みに基づいてリストからランダムなアイテムを選択します
A遺伝的アルゴリズム - 遺伝的アルゴリズムを自走車のトレーニングにどのように適用できるかの例
アルゴリズムパラダイムは、クラスの設計の基礎となる一般的な方法またはアプローチです。 アルゴリズムの。これは、アルゴリズムの概念よりも高い抽象化であり、 アルゴリズムは、コンピュータプログラムよりも高い抽象化です。
Bジャンプゲーム
Aアンバウンドナップザック問題
Aダイクストラアルゴリズム - すべてのグラフ頂点への最短経路を見つける
APrimのアルゴリズム - 重み付き無向グラフの最小スパニングツリー(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最短共通スーパーシーケンス
A0/1ナップザック問題
A整数パーティション
A最大サブアレイ
Aベルマン・フォードアルゴリズム - すべてのグラフ頂点への最短経路を見つける
Aフロイド・ワーシャルアルゴリズム - 頂点のすべてのペア間の最短経路を見つける
A正規表現マッチング
すべての依存関係をインストールする
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'
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 | 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 | n2 | n2 | 1 | はい | |
挿入ソート | n | n2 | n2 | 1 | はい | |
選択ソート | n2 | n2 | n2 | 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) | n2 | ログ(n) | いいえ | クイックソートは通常、O(log(n))スタックスペースを使用してインプレースで行われます |
シェルソート | n log(n) | ギャップシーケンスに依存 | n (log(n))2 | 1 | いいえ | |
カウントソート | n + r | n + r | n + r | n + r | はい | r - 配列内の最大数 |
基数ソート | n * k | n * k | n * k | n + k | はい | k - 最長キーの長さ |
∑ = 0
ℹ️ trekhleb.dev に関するJavaScriptとアルゴリズムに関するいくつかのプロジェクトと記事