インタビュアー: アルゴリズムについての理解について教えてください。応用シナリオ?

[[424227]]

1. 何ですか

アルゴリズムとは、問題に対する解決策の正確かつ完全な説明を指します。これは、問題を解決するための一連の明確な指示です。アルゴリズムは、問題を解決するための戦略メカニズムを説明する体系的な方法を表します。

つまり、一定の標準入力に対して、限られた時間内に必要な出力を得ることができます。

アルゴリズムに欠陥があったり、問題に対して不適切であったりする場合、そのアルゴリズムを実行しても問題は解決されません。

プログラム = アルゴリズム + データ構造。データ構造はアルゴリズム実装の基礎です。アルゴリズムは常に何らかのデータ構造に依存して実装されます。この 2 つは切り離せません。

したがって、アルゴリズムの設計と選択は、データ構造と組み合わせる必要があります。簡単に言えば、データ構造の設計とは、問題内の情報が配列に格納されるか、通常の変数またはその他のより複雑なデータ構造に格納されるかを決定するなど、格納方法を選択することです。

上記に基づいて、次のような結論を導き出すことができます。異なるアルゴリズムでは、同じタスクを完了するために異なる時間、スペース、または効率を使用する可能性があります。

2. 特徴

アルゴリズムの 5 つの主な特徴は次のとおりです。

• 有限性: アルゴリズムは、有限数のステップを実行した後に終了することが保証される必要があります。
• 明確性: アルゴリズムの各ステップには正確な定義が必要です。
• 入力: アルゴリズムには、操作オブジェクトの初期条件を特徴付ける 0 個以上の入力があります。いわゆるゼロ入力は、アルゴリズム自体が初期条件を与えることを意味します。
• 出力: アルゴリズムには 1 つ以上の出力があります。出力のないアルゴリズムは意味がない
• 有効性: アルゴリズムで実行される計算ステップは、実行可能な基本操作ステップに分解できます。つまり、各計算ステップは有限時間内に完了できます (有効性とも呼ばれます)。

3. 応用シナリオ

フロントエンド分野では、データ構造とアルゴリズムが不可欠です。たとえば、現在の Vue や React プロジェクトでは、次の単純な仮想 DOM に示すように、仮想 DOM または Fiber 構造の実装は基本的にデータ構造です。

 {
  タイプ: 'div' 、
    小道具: {
名前: 'ルシファー'  
    },
      子供たち： [{
        タイプ: 'span' 、
        プロパティ: {},
        子供たち： []
      }]
 }

Vue と React はどちらも、対応するデータ構造に基づいて diff アルゴリズムを実装できるため、フレームワーク全体のパフォーマンスとスケーラビリティが向上します。

フロントエンドのJavaScriptがコンパイルされるときも含め、対応する抽象構文木ASTが生成されます。構文自体は含まれていないため、任意の構文を任意の構文にエスケープするための対応するエスケープルールを記述するだけで済みます。これは、babel、PostCSS、prettier、typescriptでも同様です。

これらのフレームワークやツールの基盤で使用されているアルゴリズムやデータ構造は、日常業務でも広く使用されています。たとえば、関連付け機能を備えた入力ボックスは次のように実装されます。

この機能を実装したい場合は、次のようにプレフィックス ツリーを使用できます。

フロントエンドは、2 つの文字列「每日一题」と「js每日一题」の類似性を比較するなど、文字列の類似性検出を行う場合があります。この場合、「最小編集距離」アルゴリズムを使用できます。a と b の編集距離が小さいほど、それらはより類似していると考えられます。

日常生活でコードを書くときは、優れたアルゴリズム思考が必要です。適切なアルゴリズムやデータ構造を選択すると、プログラム全体の効率が向上します。

参考文献

https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025

https://lucifer.ren/blog/2019/09/18/algorthimn-fe-1/