ビデオ: ACLS Megacode 2024
John Paul Mueller、Luca Massaron
アルゴリズムは、退屈でなくても使用する必要はありません。実際には、アルゴリズムは、あなたが考えなかったさまざまな方法であなたを囲み、重要なタスクを実行するために毎日使用します。ただし、数学者にならなくてもアルゴリズムを使用できる必要があります。
プログラミング言語を使用すると、アルゴリズムの作成に使用された手順を記述できます。いくつかの言語は、コンピュータ科学者になれずに人々が理解できる方法でこのタスクを実行する際に、他の言語より優れています。 Pythonは、（パッケージ、データセット、その他のリソースを使用して）たくさんの組み込みおよび拡張サポートを提供するので、アルゴリズムの使用を容易にします。このチートシートは、アルゴリズムを迅速かつ簡単に使用するために最も一般的に必要なヒントにアクセスするのに役立ちます。
必要なアルゴリズムの検索
次の表は、さまざまな種類のデータ分析に役立つアルゴリズムとアルゴリズムの種類を示しています。
| アルゴリズム | 解説 | 有用なリンク |
| A *検索 | アルゴリズムは、ノードを探索する際にノードのコストを追跡します。 （n）999 = 999 + 999（n）999（式中、 （999）はノードに到達するコストであり、h（n）はノードに到達するための推定コストである。ノードからの目標 f（n） は、nからゴールまでの経路の推定コストです。最も有望な経路を最初に検索し、高価な経路を避けることです。 スタンフォード。 edu Balanced Tree 再編成によってバランスの取れた構造を維持し、アクセス時間を短縮できるツリーの一種。左側の要素の数は、右側の要素の数と最大で1つ異なります。
Webdoc
双方向検索 この技術は、2つの検索経路が真ん中で出会うまで、ルートノードとゴールノードから同時に検索する。このアプローチの利点は、多くの他のブルートフォース・ソリューションよりも迅速にソリューションを見つけるため、時間効率が良いことです。さらに、他のアプローチよりも効率的にメモリを使用し、常に解決策を見つけることができます。主な欠点は、実装の複雑さです。 計画。 cs バイナリツリー これは、ゼロ（リーフノード）、1つまたは2つ（分岐ノード）の他のノードに接続するノードを含むタイプのツリーです。各ノードは、データストレージ、左接続、右接続の3つの要素を定義します。 cs。 cmu。幅広い検索 この技術は、ルートノードから始まり、まず各子ノードを探索し、次に、次のレベルに移動する。それは解決策が見つかるまでレベル別に進んでいきます。このアルゴリズムの欠点は、すべてのノードをメモリに格納する必要があることです。つまり、多数のノードに相当な量のメモリを使用します。この手法では重複したノードがあるかどうかを確認できるため、時間が節約され、常に解決策が生まれます。 Khan Academcy |
ブルートフォース |
| これは、誰かが可能な限りすべての解決策を試し、最良の問題解決策を探す問題解決の技法です。ブルートフォース技法は、存在するときに最適解を保証するが、実装に時間がかかるため、ほとんどの人がそれらを回避する。 | Igm。深さ優先探索（Depth-First Search）この技法は、ルートノードから始まり、リーフノードに達するまで、接続された子ノードのセットを探索する。解決策が見つかるまで、分岐ごとに分岐を進めます。このアルゴリズムの欠点は、ノードが重複していないかどうかを確認できないことです。つまり、同じノードのパスを複数回通過する可能性があります。実際、このアルゴリズムでは解決策が見つからない場合があります。つまり、アルゴリズムが無限に検索されないようにカットオフポイントを定義する必要があります。このアプローチの利点は、メモリが効率的であることです。 | Hacker Earth |
| 分割と征服 | これは、問題を可能な限り小さなものに分割し、可能な限り単純な方法で解決する、問題解決の手法です。この技術は、ブルートフォースなどの他のアプローチと比較して、かなりの時間とリソースを節約します。ただし、必ずしも最適な結果を保証するとは限りません。 | Khan Academy |
| Dijikstra | これは、有向グラフ（正の重みを持つ）グラフの最短経路を見つけるために使用されるアルゴリズムです。 | オタクのオタク |
| グラフ | グラフは、ツリー拡張の一種です。ツリーと同様に、ノードには互いに接続して関係を作成します。ただし、バイナリツリーとは異なり、グラフには1つ以上の接続があります。実際、グラフノードには多くの場合、多数の接続があります。 GPSのマップや、ツリーのトップダウンアプローチが機能しないあらゆる種類の場所で使用されるグラフが表示されます。 | チュートリアル |
| 欲張りアルゴリズム | 問題解決プロセスのすべてのステップで解決策が最良の答えに依存する問題解決の1つ。欲張りアルゴリズムは、一般的に2つの仮定を作ります： | <！ - 3 - > |
| あるステップで単一の最適な選択をすることが可能です。各ステップで最適な選択を選択することにより、全体の問題に対する最適解を見つけることが可能である。 | チュートリアル | グリーディ・ファースト・サーチ（BFS） |
| アルゴリズムは、以下の方程式を用いてゴールに最も近い経路を常に選択する。【数9】（999） n） | 。この特定のアルゴリズムは、非常に迅速にソリューションを見つけることができますが、ループに詰まることもあります。多くの人々は、ソリューションを見つけるための最適なアプローチではないと考えています。センチュリオン2 | ハッシング |
| これは、実際にそれを探し出す前に、データ構造内の特定のデータ項目の位置を予測する方法です（構造がどのようなものであろうと）。このアプローチは、インデックスに配置されたキーの使用に依存します。ハッシュ関数は、キーをアルゴリズムがハッシュテーブルに入れる数値に変換します。ハッシュテーブルは、アルゴリズムがデータの位置を容易に予測できるように、データ構造内の要素を指すインデックスを作成する手段を提供する。 | チュートリアル | ヒープ |
| これはツリー構造にデータを挿入するための洗練されたツリーです。データ挿入を使用すると、ソートが高速になります。ツリー内に存在する最大値または最小値をすぐに提供できるツリーの能力に応じて、これらのツリーを最大ヒープおよび最小ヒープとしてさらに分類できます。ヒューリスティックス | チュートリアル | ヒューリスティック |
| これは自己発見に頼って問題解決に役立つ結果が得られる（必ずしも最適ではないが十分に良い）必要です。自己発見とは、アルゴリズムがあなたに潜在的に有用な道を示すことを可能にするプロセスです（しかし、解決策が正しいかどうかを知るためには、人間の直感と理解を重視する必要があります）。 | 北西。 edu
MapReduce
アルゴリズムを並列で（ネットワーク内で複数のコンピュータを接続して）動作させるためのフレームワークです。 Hadoop Apache |
Mergesort |
| Mergesortは、データをソートする汎用の比較ベースのメソッドです。これは、タスクを実行するための分割統治アプローチに依存します。 | オタクのオタク（Geeks for Geeks） ナッシュ均衡 これは、他の選手が他の選手の平衡戦略を知っているので、自分の戦略を変えることで誰も得られないゲーム理論です。この理論は、ゲームに勝つために他のすべてのプレイヤーが行った決定をプレイヤーが説明しなければならない敵対的な状況での使用を見ます。 Khan Academy PageRank | PageRankは、グラフ内のノードの重要度を測定するためのアルゴリズムです。このアルゴリズムは、ユーザーに関連する検索を強化するためのGoogleのコアアルゴリズムの根幹です。 |
| プリンストン。 edu | 純ヒューリスティック検索 | このアルゴリズムはノードをコストの順に展開する。それは2つのリストを維持します。閉じたリストには既に探索したノードが含まれ、開いているリストにはまだ探索しなければならないノードが含まれます。各反復において、アルゴリズムは可能な限り低いコストでノードを展開する。すべての子ノードが閉じられたリストに配置され、個々の子ノードコストが計算されます。このアルゴリズムは、低コストの子ノードをオープンリストに戻し、高コストで子ノードを削除する。結果として、このアルゴリズムは、ソリューションのインテリジェントでコストベースの検索を実行する。 |
| World of Computing | クイックソート | これは、データの配列をより小さな配列に分割することに基づく汎用ソート戦略です。これは、タスクを実行するための分割統治アプローチに依存します。 |
| チュートリアル | アンバランスツリー | これは、バランスに関係なくツリー内に必要な場所に新しいデータ項目を配置するツリーです。このアイテムを追加する方法は、ツリーの構築を高速化しますが、検索や並べ替えの際のアクセス速度を低下させます。 |
| Quora | アルゴリズムを他の数学構造と区別する | ほとんどの人と同じように、数学構造については頭を傷つけることがよくあります。それは、人々が意図的に物事を難しくしようとしているかのようです！結局のところ、方程式とは何ですか、なぜアルゴリズムと異なるのですか？まあ、恐れはありません。次の表は、あなたが遭遇するかもしれないが尋ねることを恐れている数学構造の決定的なガイドを提供します。 |
| 構造 | 説明 | 数式 |
| 全体として取ると特定の値に等しい数字と記号。方程式には常に等号が含まれているため、数字と記号が等号の反対側の特定の値を表すことがわかります。方程式には一般的にシンボルとして表示される可変情報が含まれますが、変数を使用する必要はありません。 | 式 | 情報やアイデアを表現するために使用される数字と記号の組み合わせ。数式は、通常、2つの整数の最大公約数（GCD）を定義するなど、数学的または論理的な概念を提示します（Khan Academyのビデオは、この仕組みを示しています）。一般に、数式は2つ以上の変数間の関係を示します。ほとんどの人は数式を特別な種類の方程式と見なします。 |
| アルゴリズム | 問題を解決するために使用される一連のステップ。シーケンスは、特定のソリューションを提供することによって、問題に対処するユニークな方法を提示します。アルゴリズムは、数学的または論理的概念を表す必要はありません。たとえこの方法でもっとも一般的にアルゴリズムを使用するため、本書のプレゼンテーションはそのカテゴリに入ることがよくあります。いくつかの特別な数式は、二次式などのアルゴリズムです。アルゴリズムを表すプロセスでは、次のようなものでなければなりません： | 有限： |
| アルゴリズムは最終的に問題を解決しなければなりません。よく定義される： | 一連のステップは、正確なものでなければならず、使用可能なアルゴリズムを作成することができなければならないコンピュータによって理解可能なステップを示さなければならない。 | 有効： |
| アルゴリズムは、誰かがそれを定義した問題のすべてのケースを解決する必要があります。アルゴリズムは常に解決しなければならない問題を解決する必要があります。いくつかの障害を予測する必要があるにしても、障害の発生率はまれであり、意図したアルゴリズムの使用で許容される状況でのみ発生します。 | アルゴリズムを使用する驚くべき方法 | 人々は実際には常にアルゴリズムを使用します。たとえば、このブログ記事で説明したように、トーストをアルゴリズムの一例としています。トーストを作ることは驚くべきアルゴリズムではありませんが、タスクを実行するためにコンピュータを使用する以下の表のものがあります。 |
| タスク | 驚くべき理由 | 暗号化 |
データを安全に保つことは、データソースを絶えず攻撃しているハッカーとの継続的な戦いです。アルゴリズムを使用すると、データを分析して他の形式に変換し、後で元の形式に戻すことができます。グラフ分析
2点間の最短線を決定する能力は、あらゆる用途を見出す。たとえば、経路の問題では、この特定のアルゴリズムなしではGPSは機能しませんでした。なぜなら、A地点からB地点までの最短ルートを使って都市の通りを進むことができないからです。
| 擬似乱数生成 | それは決して変化しなかった。あなたは同じ場所から出発し、同じ方法で同じステップをあなたがプレイするたびに実行します。退屈な！一見乱数を生成する能力がなければ、多くのコンピュータタスクは無意味または不可能になる。 |
| スケジューリング | 関連するすべての人に公平なリソースを使用させることは、アルゴリズムが大きな存在としてその存在を知らせる別の方法です。たとえば、交差点のタイミングライトは、軽い変更の間の秒数をカウントダウンする簡単なデバイスではなくなりました。最新のデバイスでは、時刻、気象条件、およびトラフィックの流れなど、あらゆる種類の問題が考慮されます。しかし、スケジューリングには多くの形があります。あなたのコンピュータが同時に複数のタスクを実行する方法を考えてみましょう。スケジューリングアルゴリズムがなければ、オペレーティングシステムは利用可能なすべてのリソースを取得し、アプリケーションが何らかの有用な作業を行わないようにします。 |
| 検索 | 情報を検索したり、表示された情報が必要な情報であることを確認することは、不可欠な作業です。この機能がなければ、インターネット上であなたのオフィスに完璧なコーヒーポットを販売するウェブサイトを見つけるなど、オンラインで行う多くの作業は不可能です。 |
| ソート | 情報を提示する順序を決定することは重要である。なぜなら、今日のほとんどの人は情報の過負荷に苦しみ、データの突入を減らす必要があるからである。 Amazonに行って、販売するコーヒーポットが1000本以上あることを想像しても、価格や最も肯定的なレビューに基づいてソートすることはできません。さらに、多くの複雑なアルゴリズムでは、データを適切な順序で確実に処理する必要があるため、ソートはより多くの問題を解決するための重要な要件です。
変換 ある種類のデータを別の種類のデータに変換することは、データを効果的に理解し使用する上で重要です。たとえば、帝国の重みはきちんと分かっているかもしれませんが、すべてのソースがメートル法を使用しています。 2つのシステム間の変換は、データの理解に役立ちます。同様に、高速フーリエ変換（FFT）は、時間領域と周波数領域の間で信号を変換し、WiFiルーターなどの機能を有効にします。 アルゴリズムの複雑さの扱い アルゴリズムは複雑であることはすでに知っています。しかし、複雑なものほど、実行に時間がかかりますので、アルゴリズムの複雑さを知る必要があります。次の表は、実行時間順に（最速から最速に）複雑さのさまざまなレベルを理解するのに役立ちます。 複雑さ 説明 |
定数複雑度O（1）
入力の量にかかわらず、実行時間は変わらない。各入力には1単位の実行時間が必要です。対数の複雑さO（log n）
| 操作の数は入力よりも遅くなり、小さな入力ではアルゴリズムの効率が悪くなり、大きいものでは効率が高くなります。このクラスの典型的なアルゴリズムはバイナリ検索です。 | 線形複雑さO（n） |
| 入力は1：1の比率で増加します。典型的なアルゴリズムは反復です。入力を1回スキャンしてその各要素に操作を適用すると繰り返します。線形複雑さO（n log n）999は、対数と線形の複雑さとの混合である。 Mergesortsort、Heapsort、Quicksortなど、データを注文する際に使用されるスマートなアルゴリズムの典型です。二次的複雑さO（n 999 2 999）999は、入力の数の2乗として増加する。別の反復（コンピュータサイエンスのネストされた反復と呼ばれる）の中にある反復がある場合、あなたは二次的な複雑さを持ちます。たとえば、名前のリストがあり、最も類似したものを見つけるために、それぞれの名前を他のすべての名前と比較します。効率の悪い発注アルゴリズムの中には、バブルソート、選択ソート、挿入ソートという複雑さがあります。このレベルの複雑さは、アルゴリズムがソリューションに達する前に数時間または数日間実行される可能性があることを意味します。立方体の複雑さO（n | 399） |
| 複数のネストされた反復を持つため、操作は二次的複雑さよりもさらに速くなります。アルゴリズムがこのような複雑さを持ち、適度な量のデータ（100,000要素）を処理する必要がある場合、アルゴリズムは何年も実行される可能性があります。入力の威力である操作の数が多い場合は、アルゴリズムを多項式時間で実行することが一般的です。指数関数的複雑度O（2 999 n 999）このアルゴリズムは、新たに追加されたすべての要素に対して2倍の前の演算を行う。アルゴリズムにこのような複雑さがある場合、小さな問題でさえも永遠にかかることがあります。網羅的な検索を行う多くのアルゴリズムは指数関数的に複雑です。しかし、この複雑さの古典的な例は、フィボナッチ数の計算です。このアルゴリズムは、要素間の可能な組み合わせの数が多いため、複雑さの実質的な悪夢を提示する。ちょっと想像してみましょう：あなたの入力が100個のオブジェクトで、コンピュータの操作が10 999 - 6 999秒（今日のすべてのコンピュータで妥当な速度）であれば、約10 140 999年（宇宙の年齢は10 999 14 999年と推定されるため、不可能な時間です）。有名な要因の複雑さの問題は、セールスマンが多くの都市を訪れて出発都市に戻るための最短ルートを見つけなければならない、旅行セールスマンの問題です。 |
