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

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


ティッカー コデコフ

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

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

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

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

データ構造

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

B
- 初心者、 - 上級者
A

アルゴリズム

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

B
- 初心者、 - 上級者
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'

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.

Big O graphs

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 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 - 最長キーの長さ

プロジェクト支援者

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

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

∑ = 0

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

著者