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
License: MIT

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

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

CI codecov

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

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

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

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

データ構造

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

B
-初心者、
A
-上級者

アルゴリズム

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

B
-初心者、
A
-上級者

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

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

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

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

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

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表記で指定されたアルゴリズムの最も一般的な成長順序を見つけることができます。

ビッグOグラフ

出典: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 2 n 2 1 はい
挿入ソート n n 2 n 2 1 はい
選択ソート n 2 n 2 n 2 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 2 log(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-最長のキーの長さ

プロジェクト支援者

このプロジェクトをサポートすることができます❤️️GitHubまたは_❤️️Patreon 。_

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

∑ = 0

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