フロントエンドアルゴリズム入門 -- データ構造編

基礎編

1) アルゴリズムとはどういう意味ですか？

アルゴリズムとは、計算や問題を解くための段階的なプロセスのことです。

2) アルゴリズムとプログラムの違いは何ですか？

その違いは、プログラムはコンピュータが理解できるプログラミング言語で書かれ、コンピュータ上で実行できるのに対し、アルゴリズムは人間が理解できる数学的な方法で記述され、プログラミングに使われるということです。しかし、アルゴリズムとプログラミングの間に特定の境界線はありません。

3) アルゴリズムの選び方

開発者によって同じ問題でも解き方が違いますし、プログラミング言語によっても書き方が違います。 アルゴリズムの判断基準を設ける目的は、最も良い基準のアルゴリズムを選ぶことです。アルゴリズムの判定基準は2つあり、1つは結果が計算されるまでアルゴリズムを実行するのにかかる空間の量、もう1つは結果が計算されるまでアルゴリズムを実行するのにかかる時間の量です。これらはそれぞれ、空間の複雑さ、時間の複雑さと呼ばれます。一般に、複雑度が低いほどメモリの消費量が少なく、実行速度が速く、理解しやすい。一般に、最も重要視されるのはアルゴリズムの実行時間です。

4) アルゴリズムの実行時間はどのように反映されますか？

異なるアルゴリズム、異なる機器、データの異なる量は、アルゴリズム時間の違いにつながる、実行時間の理論を介して計算される多項式であり、最も直感的にデータ量の変化と時間の関係を理解できるようにする必要があり、多くの場合、重要でない項目を無視して、式の実行時間の傾向の最も単純で最も反映を取得するには、置く：重要でない項目を無視して、データ量の変化と実行時間の最も単純な式この関係はOの形で書かれ、Oは大文字で、内容以外の重要な項を無視することを示し、順序で発音し、nはアルゴリズムに関係するデータ量を示します。

データ構造

なぜ複数のデータ構造を持つことが重要なのですか？

使用目的に応じてデータ型を使い分けることで、メモリ空間を有効活用できます。

)連鎖テーブル

連鎖表はデータ構造の一つで、そのデータは線形に配置されます。メモリ空間では、データはメモリストレージに散在し、各データは2つの部分から構成され、1つの部分はデータ自体であり、もう1つの部分はポインタであり、ストレージ空間の次の部分を指します。データにアクセスする時、ポインタが一つずつ下を指すのを追うだけで、最後まで見つけるか、アクセスするまで、もし連鎖表のデータ量がnなら、データを見つけるには、最速の時間を必要とし、最大でも、n回探す必要があります。連鎖表のデータを追加または削除する必要がある時、1つまたは2つのデータポインタを変更するだけで、連鎖表のデータ量とは関係なく、一定のレベルです。その。

要約します：

連鎖表のデータは線形であり、記憶空間は不連続であり、アクセスの時間の複雑さはOであり、追加と削除の時間の複雑さはO（1）です。

拡張：

円形連鎖表: 連鎖表の末尾のデータはポインタなし、連鎖表の先頭のデータへのポインタが末尾のデータに対して追加されると、連鎖表のポインタ間にリング構造が形成され、円形連鎖表またはリング型連鎖表と呼ばれます。

双方向連鎖表：連鎖表内のポインタが、前のデータから次のデータへ、また、後の要素から前のデータへ指すことができる場合、双方向連鎖表が形成されます。

ここで注意：与えられた定義では、データはデータ本体とポインタから構成され、ポインタが増加すると、データはより多くの記憶領域を必要とすることも増加し、それはより多くのメモリを占有すると言われています。同時に、より多くのポインタが、データを追加または削除するときに、より複雑なポインタを変更する必要があり、より多くのポインタを指すように変更する必要があります。

) 配列

配列も線形に配列されたデータ構造の1つで、リンクリストとは異なり、メモリ空間における配列の格納は連続的です。配列に追加する場合、配列の先頭に追加すると、まず配列を展開する必要があります。同様に、要素を削除する場合は、末尾をO、先頭をOとして削除します。連鎖表に比べて、配列は照会が簡単ですが、操作の複雑さは高くなります。

スタック

スタックは線形データ構造で、スタックに要素を追加する時、この要素はスタックの一番上に追加され、要素を削除する時、一番上の位置から一方的に読み取るだけで、要素の後ろを読み取ることができ、つまり、最後に追加されるのではなく、最初に読み取ることができ、したがって、スタックはLIFOモードとして知られており、データを追加したり削除したりする方法は、スタックに出入りする方法としても知られています。スタックの LIFO 特性のために、それはしばしば最新のデータを保存するために使用されます。

キュー

キューはまた、データ構造の線形構造であり、それはスタックに非常によく似ていますが、一方向順序付け操作は、しかし、最初のアウトの後、キューは、キューと同じように、最初のバックで後の行の前に来て、先入れ先出しに属し、要素の背面にアクセスするには、唯一の要素の前にアクセスすることができますターゲット要素へのアクセスの終了前にアクセスされます。追加および削除キュー操作はまた、キュー内とキュー外として知られています。

5) ハッシュテーブル

ハッシュテーブルは、キーと値のペアの組み合わせでデータを格納し、一般的に、データのアイデンティティとしてのキーと、データの内容としての値。ハッシュテーブルは通常、ハッシュ関数と組み合わせて使用されます。ハッシュテーブルを確立する過程で、ハッシュ関数を使用して配列に存在するデータのハッシュ値を計算する必要があります。

ハッシュテーブルを使用すると、配列の検索が高速化され、柔軟性と効率性の面で大きな利点があります。プログラミングでは、配列を関連付けるときにハッシュテーブルがよく使われます。

ヒープ

ヒープはグラフの一種で、2次元のデータ構造であり、その概略は2ビットの樹形図で表すことができ、子ノードのデータ値は常に親ノードより大きくなります。また、データを取り出した後、最後のデータを一番上に移動させ、その大きさを子ノードのデータと比較しながら下に移動させる必要があるため、データを取り出すのに必要な実行時間は、ヒープの特徴から、データ量をnとすると、木の高さに比例します。これは、ツリーの高さがlog2nであることがわかりますが、その後、ツリーを再構築する複雑さはOです。同じことが、データを追加するために適用され、ヒープの最後にデータを追加し、親ノードのサイズと比較しながら、データを移動しながら、上まで、ヒープの条件を満たすために知っています。

頻繁にデータから最小値を削除する必要がある場合は、ヒープ、良い選択です。

7) バイナリ探索木

バイナリー・ルックアップ・ツリーは、バイナリー・サーチ・ツリー、バイナリー・ソート・ツリーとも呼ばれます。これは2次元のグラフ構造です。各ノードは左サブツリーと右サブツリーと呼ばれる最大2つのノードを持ち、各ノードの値はその左サブツリーの値より大きく、各ノードの値はその右サブツリーの値より小さいという事実によって特徴付けられます。

これらの2つの特徴によると見ることができます：バイナリ検索ツリーは、見つけるために左下の端に最小値を見つけるために、見つけるために右下の端に最大値を見つけます。

まとめ

データ構造は、最終的に使用目的を決定するために選択するために、フロントエンドは、一般的に上記の7つのために使用され、具体的にはどのように柔軟にこれらのデータ構造を使用するには？何ができるのでしょうか？次回のエピソードをご覧ください。