DataStructure And Algo
1.0.0
データ構造は、保存されたデータの操作をより効率的に実行できるように、コンピューターにデータを整理および保存する特別な手段です。データ構造は、コンピューターサイエンスとソフトウェアエンジニアリングの分野で、幅広く多様な使用範囲を備えています。データ構造は、開発されたほぼすべてのプログラムまたはソフトウェアシステムで使用されています。さらに、データ構造は、コンピューターサイエンスとソフトウェアエンジニアリングの基本に基づいています。ソフトウェアエンジニアリングのインタビューの質問に関しては、これは重要なトピックです。したがって、開発者として、データ構造について十分な知識が必要です。
配列は、同じデータ型のアイテムを保持できる固定サイズの構造です。整数の配列、浮動小数点数の配列、文字列の配列、またはアレイの配列（2次元配列など）でもあります。配列はインデックス化されています。つまり、ランダムアクセスが可能です。
アレイから要素を配列に挿入し、配列から要素を削除することは、配列のサイズが固定されているため、すぐに実行することはできません。アレイに要素を挿入する場合は、最初にサイズが大きくなった新しい配列（電流サイズ + 1）を作成し、既存の要素をコピーして新しい要素を追加する必要があります。同じことが削除についても、サイズが縮小された新しい配列があります。
リンクリストは、互いにリンクされた線形順序のアイテムのシーケンスで構成されるシーケンシャル構造です。したがって、データに順次アクセスする必要があり、ランダムアクセスは不可能です。リンクされたリストは、動的セットのシンプルで柔軟な表現を提供します。
スタックはLIFO （最初は最後に、最後に配置された要素に最初にアクセスできます）構造で、多くのプログラミング言語で一般的に見つけることができます。この構造は、実際のスタック、つまりプレートのスタックに似ているため、「スタック」と呼ばれます。
発現評価に使用されます（例：数学的式の解析と評価のためのシャントヤードアルゴリズム）。再帰プログラミングに関数呼び出しを実装するために使用されます。
キューはFIFOです（最初は最初に、最初に配置された要素にアクセスできます）構造は、多くのプログラミング言語で一般的に見つけることができます。この構造は、実際のキュー、つまりキューで待っている人々に似ているため、「キュー」と呼ばれます。
マルチスレッドのスレッドを管理するために使用されます。キューイングシステムを実装するために使用されます（例：優先キュー）。
ハッシュテーブルは、それぞれに関連付けられたキーを持つ値を保存するデータ構造です。さらに、値に関連するキーを知っていれば、検索を効率的にサポートします。したがって、データのサイズに関係なく、挿入と検索において非常に効率的です。
直接アドレス指定は、テーブルに保存するときに、値とキーの間の1対1のマッピングを使用します。ただし、キー価値のペアが多数ある場合、このアプローチには問題があります。テーブルは非常に多くのレコードで巨大であり、典型的なコンピューターで利用可能なメモリを考えると、非現実的または保存することさえ不可能になる場合があります。この問題を回避するために、ハッシュテーブルを使用します。
ハッシュ関数（h）という名前の特別な関数を使用して、直接アドレス指定における前述の問題を克服します。直接アクセスでは、キーKの値がスロットkに保存されます。ハッシュ関数を使用して、各値が進むテーブル（スロット）のインデックスを計算します。特定のキーのハッシュ関数を使用して計算される値は、値がマッピングされているテーブルのインデックスを示すハッシュ値と呼ばれます。
ツリーは、データが階層的に編成され、リンクされている階層構造です。この構造はリンクされたリストとは異なりますが、リンクされたリストでは、アイテムは線形順序でリンクされます。特定のアプリケーションに合わせて特定の制約を満たすために、過去数十年にわたってさまざまな種類の木が開発されてきました。いくつかの例には、バイナリ検索ツリー、Bツリー、TREAP、赤黒ツリー、スプレイツリー、AVLツリー、n-aryツリーがあります。
名前が示すように、バイナリ検索ツリー（BST）は、データが階層構造で編成されるバイナリツリーです。このデータ構造は、並べ替えられた順序で値を保存します。バイナリ検索ツリー内のすべてのノードは、次の属性を構成します。
バイナリ検索ツリーは、それを他の木と区別するユニークなプロパティを展示します。このプロパティは、** binary-search-treeプロパティ**として知られています。
ヒープは、親ノードが子供と比較され、それに応じて配置されているバイナリツリーの特殊なケースです。
ヒープには2つのタイプがあります。
グラフは、頂点またはノードの有限セットと、これらの頂点を接続するエッジのセットで構成されています。
グラフの順序は、グラフ内の頂点の数です。グラフのサイズは、グラフ内のエッジ数です。
同じエッジで互いに接続されている場合、2つのノードが隣接すると言われています。
グラフGは、すべてのエッジが開始頂点と端頂点とは何かを示す方向を示す方向に指示されたグラフと言われています。 （u、v）は頂点uからのインシデントまたは出発であり、頂点v。自己ループに入射または入ると、頂点からそれ自体へのエッジであると言います。
グラフGは、すべてのエッジに方向がない場合、無向グラフと言われています。 2つの頂点の間で両方の方法で進むことができます。
頂点がグラフ内の他のノードに接続されていない場合、分離されていると言われています。
Trieは、ノードがアルファベットの文字を保存するツリーのような情報検索データ構造です。また、デジタルツリーまたは基数ツリーまたはプレフィックスツリーとしても知られています。
Trieは、効率的な情報検索データ構造です。 Trieを使用して、検索の複雑さを最適な制限（キーの長さ）にすることができます。キーをバイナリ検索ツリーに保存する場合、バランスの取れたBSTはm * log nに比例する時間が必要です。ここで、mは最大文字列長、nはツリーのキー数です。 Trieを使用して、O（M）時間でキーを検索できます。
1。標準Trie ：データ構造のような順序付けられたツリーです。
2。圧縮Trie ：スペースの最適化を実現するために使用されます。圧縮されたTrieは、標準のTrieの高度なバージョンです。
3。接尾辞Trie ：接尾辞Trieは、圧縮されたTrieの高度なバージョンです。
Trieを使用すると、l（l）時間で文字列を挿入して見つけることができます。ここで、lは単語の長さを表します。これは明らかにBSTよりも高速です。これは、実装された方法のために、ハッシュするよりも高速です。ハッシュ機能を計算する必要はありません。 Trieのもう1つの利点は、すべての単語をアルファベット順の順序で簡単に印刷できることです。これは、ハッシュで簡単に不可能です。
ダイナミックプログラミングは、問題をサブ問題に分割し、将来の目的で結果を保存するため、結果を再度計算する必要がないようにする手法です。サブ問題は、全体的なソリューションを最適化するために最適化されています。最適な下部構造特性として知られています。動的プログラミングの主な使用は、最適化の問題を解決することです。ここで、最適化の問題は、問題の最小または最大の解を見つけようとしていることを意味します。動的プログラミングは、ソリューションが存在する場合、問題の最適なソリューションを見つけることを保証します。
時間の複雑さアルゴリズムo（1）配列の特定の要素を検索します。たとえば、印刷（my_array [97]）アレイのサイズに関係なく、要素を直接調べることができます。1つの操作が必要です。 （これは実際にはアルゴリズムではありませんが、時間の複雑さがどのように機能するかを理解するのに役立ちます。）
o（n）最低値を見つける。アルゴリズムは、各値を1回比較する必要があるため、アルゴリズムはn値を持つ配列でn操作を実行する必要があります。
o（n 2）バブルソート、選択ソート、および挿入ソートは、この時間の複雑さのアルゴリズムです。それらの時間の複雑さの理由は、これらのアルゴリズムのページで説明されています。
大規模なデータセットは、これらのアルゴリズムを大幅に遅くします。 Nが100から200の値に増加するだけで、操作の数は30000も増加する可能性があります！
o（n log n）QuickSortアルゴリズムは、上記の3つのソートアルゴリズムよりも平均して高速であり、O（n log n）は平均であり、最悪の場合ではありません。 QuickSortの最悪の場合はO（N 2）ですが、クイックソートを非常に興味深いものにするのは平均時間です。 QuickSortについては後で学びます。
参照はこのリンクから取得されます - sourav saini？
