ブルートフォースアルゴリズムの説明

ブルートフォースアルゴリズムは、まさにそのように聞こえます。効率を向上させるための高度な手法ではなく、純粋な計算能力に依存する問題を解決し、あらゆる可能性を試す簡単な方法です。

たとえば、それぞれ0〜9の4桁の小さな南京錠があるとします。組み合わせを忘れましたが、別の南京錠を購入したくありません。どの数字も思い出せないため、ブルートフォース方式を使用してロックを開く必要があります。

したがって、すべての番号を0に戻し、開くまで0001、0002、0003などの番号を1つずつ試します。最悪のシナリオでは、104、つまり10,000回の試行で組み合わせを見つける必要があります。

コンピュータサイエンスの典型的な例は、巡回セールスマン問題(TSP)です。セールスマンが全国の10都市を訪問する必要があるとします。総移動距離が最小になるように、これらの都市を訪問する順序をどのように決定しますか?

強引な解決策は、考えられるすべてのルートの合計距離を計算してから、最短ルートを選択することです。巧妙なアルゴリズムによって多くの可能なルートを排除することが可能であるため、これは特に効率的ではありません。

ブルートフォースの時間計算量はO(m n であり、O(n * m)と表記されることもあります。。したがって、ブルートフォースを使用して「m」文字の文字列から「n」文字の文字列を検索する場合、n * m回の試行が必要になります。

アルゴリズムに関する詳細情報

コンピュータサイエンスでは、アルゴリズムは、特定の問題を解決するための一連のステップバイステップの手順です。アルゴリズムは、計算の実行、データの処理、または自動推論タスクの実行を目的として設計できます。

ウィキペディアがそれらを定義する方法は次のとおりです。

アルゴリズムは、有限の空間と時間内で、関数を計算するための明確に定義された形式言語で表現できる効果的な方法です。初期状態と初期入力(おそらく空)から開始して、命令は、実行されると、有限数の明確に定義された連続状態を経て、最終的に「出力」を生成し、最終終了状態で終了する計算を記述します。ある状態から次の状態への移行は、必ずしも決定論的ではありません。ランダム化アルゴリズムとして知られる一部のアルゴリズムには、ランダム入力が組み込まれています。

アルゴリズムが従わなければならない特定の要件があります。

  1. 明確性:プロセスの各ステップは正確に記述されています。
  2. 効果的な計算可能性:プロセスの各ステップは、コンピューターで実行できます。
  3. 有限性:プログラムは最終的に正常に終了します。

いくつかの一般的なタイプのアルゴリズムは次のとおりです。

  • ソートアルゴリズム
  • 検索アルゴリズム
  • 圧縮アルゴリズム。

アルゴリズムのクラスには次のものが含まれます

  • グラフ
  • 動的計画法
  • 並べ替え
  • 検索中
  • 文字列
  • 数学
  • 計算幾何学
  • 最適化
  • その他。

技術的にはアルゴリズムのクラスではありませんが、データ構造はしばしばそれらとグループ化されます。

効率

アルゴリズムは、最も一般的には、その効率と、タスクを完了するために必要なコンピューティングリソースの量によって判断されます。

アルゴリズムを評価する一般的な方法は、その時間計算量を調べることです。これは、入力サイズが大きくなるにつれてアルゴリズムの実行時間がどのように長くなるかを示しています。今日のアルゴリズムは大規模なデータ入力で動作する必要があるため、アルゴリズムの実行時間が適度に速いことが不可欠です。

ソートアルゴリズム

並べ替えアルゴリズムには、必要に応じてさまざまな種類があります。非常に一般的で広く使用されているものは次のとおりです。

クイックソート

クイックソートなしで終了できるソートの議論はありません。基本的な概念は次のとおりです。クイックソート

マージソート

配列をソートする方法の概念に依存するソートアルゴリズムは、1つのソートされた配列を与えるためにマージされます。詳細はこちら:マージソート

freeCodeCampのカリキュラムは、アルゴリズムの作成に重点を置いています。これは、アルゴリズムの学習がプログラミングスキルを練習するための良い方法であるためです。面接官は、最も一般的には、開発者の就職の面接中にアルゴリズムで候補者をテストします。

JavaScriptのアルゴリズムに関する本:

JavaScriptのデータ構造

  • JavaScriptのデータ構造をカバーする無料の本
  • GitBook

JavaScriptデータ構造とアルゴリズムの学習-第2版

  • オブジェクト指向プログラミング、プロトタイプの継承、並べ替えと検索のアルゴリズム、クイックソート、マージソート、二分探索木、高度なアルゴリズムの概念について説明します。
  • アマゾン
  • ISBN-13:978-1785285493

JavaScriptを使用したデータ構造とアルゴリズム:従来のコンピューティングアプローチをWebにもたらします

  • 再帰、ソートと検索のアルゴリズム、リンクリスト、バイナリ検索ツリーについて説明します。
  • アマゾン
  • ISBN-13:978-1449364939