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ずアルゎリズムに関するいく぀かのプロゞェクトず蚘事