データ構造とアルゴリズムの基本概念

  [[361250]]

この記事はWeChatの公開アカウント「bigsai」から転載したもので、著者はbigsaiです。この記事を転載する場合はbigsai公開アカウントまでご連絡ください。

序文

データ構造とアルゴリズムは、プログラマーの内面的な力を反映する重要な基準の 1 つであり、データ構造もさまざまな側面で応用されています。業界では、プログラム = データ構造 + アルゴリズムという方程式さえあります。さまざまなミドルウェア開発者やアーキテクトが、ミドルウェア、プロジェクト構造、アルゴリズムを最適化して動作効率を向上させ、メモリ使用量を削減するために懸命に取り組んでいます。ここではデータ構造が非常に重要な役割を果たします。さらに、データ構造にはオブジェクト指向の考え方も含まれているため、データ構造を学習して習得すると、論理的思考と抽象処理能力が大幅に向上します。

なぜデータ構造とアルゴリズムを学ぶのでしょうか? あなたがまだ学生であれば、このコースは必修コースであり、基本的に大学院入学試験の必須科目です。社内競争が激しい大企業への就職活動においては、面接や筆記試験で求められる、データ構造やアルゴリズムも非常に重要な審査ポイントとなります。データ構造やアルゴリズムに取り組むことは、内面的な強さを向上させるための非常に重要な現れでもあります。プログラマーにとって、満足のいく結果を得たいのであれば、データ構造とアルゴリズムは必須のスキルです。

データ構造

コンセプト

データ構造とは、コンピューターがデータを保存および整理する方法です。データ構造とは、1 つ以上の特定の関係を持つデータ要素の集合です。多くの場合、データ構造を慎重に選択すると、運用効率やストレージ効率が向上します。

つまり、データ構造とは、特定の実行ルールに従い、特定の実行アルゴリズムと組み合わせて一連のストレージ構造によって形成される効率的なストレージ構造です。私たちがよく知っているリレーショナル データベース、非リレーショナル データベース、検索エンジン ストレージ、メッセージ キューなどは、すべて大規模データ構造の優れた応用例です。もちろん、これらのアプリケーション ミドルウェアでは、単純な構造上の問題以上のものを考慮する必要があります。実際の OS やネットワークなどの他の要素も考慮されます。

データ構造とアルゴリズムに関するコラムについて。私たちプログラマーが最初に変更して習得するのは、メモリ内で動作する抽象データ構造です。線形構造、ツリー、グラフなど、比較的単一のデータ構造タイプです。

関連用語

データ構造とアルゴリズムでは、データ、データ オブジェクト、データ要素、データ項目間の関係について混乱している人が多くいます。絵を描いて説明し、その後、例を挙げて皆さんと共有したいと思います。

ユーザー情報テーブル ユーザー

リストlist; //データオブジェクトリスト

クラスユーザー
{
     //わずかに
整数ID;
     文字列名;
     ストリングセックス;
 }
 //リストと女性はデータです
List<users>list;//データオブジェクトリスト
List<users>woman; //データオブジェクト woman
 list.add (new users(001, "bigsai" , "man" )); //データ要素を追加 users は 3 つのデータ項目 (001、bigsai、man) で構成されています
list.add (new users(002, "smallsai" , "man" )); //データ要素
list.add (new users(003, "菜虚坤" , "woman" )); //データ要素
woman.add (list.get(2)); //003、 「菜虚坤」 、 「woman」は3つのデータ項目からなるデータ要素です

データ: 客観的な事物の記号表現。コンピューターに入力してコンピューター プログラムで処理できるすべての記号の集合を指します。上記の表の 3 つのユーザー情報レコードはデータです (複数の表と複数のコレクションが存在する場合もありますが、ここでは 1 つだけです)。これらのデータは通常、ユーザーによって入力されるか、カスタム構築されます。もちろん、画像や音声もデータです。

データ要素: データ要素はデータの基本単位です。データ要素は複数のデータ項目で構成されます。これは、pojo オブジェクトまたはデータベース内のレコードとして考えることができます。たとえば、Caixukun のレコードはデータ要素です。

データ項目: ユーザーを構成するフィールド/属性には、ID、名前、性別などが含まれます。これらはデータ項目です。データ項目は、データ要素を構成する最小の分割不可能なフィールドです。これは、pojo オブジェクトまたはテーブル (people) の属性/フィールドの値として見ることができます。

データ オブジェクト: 同じプロパティを持つデータ要素のコレクション。データのサブセットです。たとえば、上記の users テーブル、list コレクション、woman コレクションはすべてデータ オブジェクトです。単一のテーブルまたはコレクションをデータ オブジェクトにすることができます。

一般的に言えば、データの範囲は最も広いです。すべてのデータはデータであり、データ オブジェクトは同じプロパティを持つセットにすぎません。このセットはデータのサブセットですが、データの基本単位ではありません。データ要素がデータの基本単位です。たとえば、猫のテーブルと犬のテーブルはどちらもデータであり、猫のテーブルはデータ オブジェクトです (どちらも猫のようなオブジェクトを記述するため)。ただし、データの基本単位は猫と犬ではなく、子猫 1 号、大型猫 2 号、ハスキー 1 号、チベタン マスティフ 2 号など、それぞれの特定の項目がデータの基本単位です。

データ型と抽象データ型は混同しやすいので、区別してください。

データ型

アトミック型: 値を部分に分割できない型。たとえば、int、char、double、float などです。

構造化型: 値を複数のコンポーネントに分割できるデータ型。構造体の各種構造など。

抽象データ型 (ADT): 抽象データ型 (ADT) は、データ要素を格納するためのストレージ構造と、基本操作を実装するためのアルゴリズムを含む実装です。これにより、実装の詳細を考慮せずに構造のみを研究して使用することが可能になります。たとえば、List、Map、Set などを使用する場合、その API とプロパティおよび関数を理解するだけで済みます。具体的な実装は異なるソリューションになる場合があります。たとえば、List の実装には、配列やリンク リストなどのさまざまなオプションがあります。

3つの要素

論理構造: データ要素間の論理関係。論理構造は線形構造と非線形構造に分けられます。線形構造には、順次リスト、リンク リストなどがあります。非線形性とは、集合、ツリー、グラフなどの構造を指します。

ストレージ構造: コンピューター内のデータ構造の表現 (イメージとも呼ばれ、物理構造とも呼ばれます)。ストレージ構造は、主にシーケンシャル ストレージ、チェーン ストレージ、インデックス ストレージ、ハッシュ ストレージに分けられます。これらの種類のストレージは、次の図で簡単に理解できます (理解のためだけのもので、これ以上の考慮はありません)。

データ操作: データに適用される操作には、操作の定義と実装が含まれます。操作の定義は論理構造に基づいており、操作の実装はストレージ構造に基づいています。

ここで混同しやすいのは、論理構造とストレージ構造の概念です。論理構造については、論理という言葉を見ることは難しくありません。論理関係とは、線形構造や非線形構造など、物理的なアドレスの関係を考慮せずに、2つがデータ関係に存在することを意味します。これは、データの集合における接続の方法と形式を説明し、データを対象とします。重要なのは、データ構造の機能です。たとえば、線形リストは最初から最後まで順序付けられています。順序付けられたセットが必要な場合は、線形リストを使用できます。

ストレージ構造は物理アドレスにリンクされています。同じ論理構造でも、異なるストレージ構造で実装すると、適用可能なシナリオやパフォーマンスが異なる場合があります。たとえば、同じ線形リストの場合、ストレージ構造を実装する方法が複数ある場合があります。たとえば、シーケンシャル リストとリンク リスト (Arraylist、Linkedlist) のストレージ構造は異なります。一方はシーケンシャル ストレージ (配列) で実装され、もう一方はリンク ストレージ (リンク リスト) で実装されます。これは、コンピュータが実行される物理アドレス間の関係に関係します。しかし、通常、同じタイプのストレージ構造によって実装されたいくつかのデータ構造には、いくつかの類似した共通点と欠点があります (線形は検索は簡単ですが挿入は難しく、チェーンは挿入は簡単ですが検索は難しいなど)。

アルゴリズム分析

上記では、データ構造に関連する概念について説明しました。次に、アルゴリズム分析のいくつかの概念について説明します。

アルゴリズムの 5 つの重要な特性: 有限性、決定論、実現可能性、入力、出力。これらは文字通りの意味から理解できます。有限性は、アルゴリズムに終わりがあり、無限にループできないことを強調します。決定性は、各命令に意味があり、同じ入力が同じ出力を生成することを意味します。実行可能性は、アルゴリズムの各ステップが複数回の実行後に実装できることを意味します。入力は 0 個以上の入力 (0 の場合もあります) です。出力は 1 個以上の出力 (出力がなければなりません) です。

優れたアルゴリズムは通常、効率性とスペース リソースの使用 (時間の複雑さと空間の複雑さ) に重点を置いています。複雑さは通常、桁数で表され、具体的な数値で表されることはほとんどありません。

空間の複雑さ

概念: アルゴリズムが動作中に一時的に占有する記憶領域の量の尺度であり、S(n)=O(f(n)) として記録されます。

実際、アルゴリズムの測定において空間計算量が占める割合は比較的低いですが (時間のために空間を犠牲にするデータ構造やアルゴリズムがよく使用されます)、空間計算量の重要性を無視することはできません。問題解決においても、実際のプロジェクト制作においても、記憶力は大きな指標となります。これは特に Java に当てはまります。メモリ自体が大きく、使用するストレージロジックが適切でない場合は、システムリソースを多く占有し、サービスに負担をかけます。

多くの場合、アルゴリズムは時間（効率）と引き換えにスペースを犠牲にします。たとえば、よく知られている文字列マッチングの String.contains() メソッドは、時間の計算量が O(n^2) で、追加のメモリを必要としないブルート フォース クラッキング メソッドであることは誰もが知っています。 KMP アルゴリズムは、効率と速度の点でブルート フォース方式よりも優れていますが、KMP ではマークされたストレージ操作に他の配列 (next[]) を使用する必要があります。オーバーヘッドのスペースが使用されます。もう 1 つの例はマージ ソートです。マージ ソートでも、新しい配列を使用して再帰パーティショニングで段階的な計算を実行し、効率を向上させますが、メモリのオーバーヘッドがわずかに発生します。

もちろん、アルゴリズムの最大スペース消費量は、JVM によって設定された最大値 (通常は 2G) を超えることはできません。(2147483645) 2 次元配列または複数の多次元データを開く場合は、大きすぎるサイズで開かないでください。ヒープ OutOfMemoryError が発生する可能性があります。

時間計算量

概念: コンピュータ サイエンスでは、アルゴリズムの時間計算量は、アルゴリズムの実行時間を定性的に説明する関数です。これは、アルゴリズムへの入力値を表す文字列の長さの関数です。時間の計算量は、関数の低次の項と先頭の係数を除外するビッグ O 表記法を使用して表現されることが多いです。このように使用すると、入力値のサイズが無限大に近づいたときに何が起こるかを考慮すると、時間の計算量は漸近的であると言われます。

ソートの時間計算量: O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

一般的な時間計算量: 多くの人は時間計算量の概念が漠然としています。次の例は、いくつかの時間の複雑さを示しています。

O(1): 定数関数

• 15 = 15

O(logn): 対数関数

• for(int i=1;i
• 典型的な二分探索、拡張ユークリッド、高速べき等アルゴリズムもあり、これらはすべて O(logn) です。高効率アルゴリズムです。

O(n): 線形関数

• (int i=0;iの場合
• これは非常に一般的であり、ほとんどの問題をうまく解決できます。

O(nlogn):

• (int i=1;iの場合
• クイック ソートやマージ ソートなど、多くの一般的なソート アルゴリズムは通常 nlogn です。このアルゴリズムもほとんどの場合非常に効率的です。

（n^2）

• for(int i=0;i
• 実際、O(n^2) の効率はあまり良くありません。大きなデータの場合、O(n^2) またはそれ以上の累乗ではパフォーマンスが低下します。

もちろん、n=10000 の場合、実行時間や、時間計算量の異なるアルゴリズムの時間も異なります。

アルゴリズムの複雑さを軽減するには、バイナリソートツリーの検索、セグメントツリーの動的ソートなど、データ構造の特性と利点に頼る必要がある場合があります。これらのデータ構造は、特定の問題を解決する際に非常に優れたパフォーマンスを発揮します。その他はアルゴリズム戦略によって解決されます。たとえば、ソートの場合、バブルソートのような単純で単純な方法は O(n2) ですが、クイックソートやマージのようなスマートな方法は O(nlogn) になります。速度を上げるには、より高度なデータ構造とより洗練されたアルゴリズムを習得する必要があります。

時間の計算量 時間の計算量の計算の一般的な手順は次のとおりです。1. 実行時間が最も長いステートメントを見つけます。2. ステートメント実行の大きさの順序を計算します。3. O を使用して結果を表します。ルールは 2 つあります。

追加ルール: 同じプログラム内に複数の並列実行ステートメントがある場合は、最大のものを選択します。例:

 T(n)=O(m)+O(n)=最大(O(m),O(n));
 T(n)=O(n)+O(nlogn)=最大(O(n),O(nlogn))=O(nlogn);

乗算ルール: ループ構造、時間計算量は乗算によって計算されます。例:

 T(n)=O(m)*O(n)=O(mn)
 T(n)=O(m)*O(m)=O(m^2)( forループの2層)

もちろん、多くのアルゴリズムの時間計算量は入力データにも関連しており、最適な時間計算量（実行可能な回数が最も少ない場合）、最悪の時間計算量（実行回数が最も少ない場合）、平均時間計算量に分類できます。これはソートアルゴリズムで具体的に分析されていますが、通常は平均時間計算量を使用してアルゴリズムの品質を測定します。

データ構造とアルゴリズムの学習

データ構造とアルゴリズムの基本概念を紹介した後、データ構造とアルゴリズムの学習という観点から、以下に古典的なデータ構造とアルゴリズムの学習プロセスの手順を書き留めて、参考になれば幸いです。

データ構造

• 単一リンクリスト（ヘッドノードあり、ヘッドノードなし）の設計と実装（追加、削除、変更、クエリ）、二重リンクリストの設計と実装
• スタックの設計と実装 (配列とリンク リスト)、キューの設計と実装 (配列とリンク リスト)
• 二分木の概念学習、二分木の事前順序、順序、事後順序のトラバーサルの再帰的、非再帰的実装、レベル順序のトラバーサル
• バイナリソートツリー（挿入と削除）の設計と実装
• ヒープ（優先キュー、ヒープソート）
• AVL（バランス）ツリーの設計と実装（4つのスピン方法の理解と実装）
• ストレッチツリーと赤黒ツリーの概念を理解する
• B.B+ 原理概念の理解
• ハフマン木原理（貪欲戦略）の概念的理解
• ハッシュ（ハッシュテーブル）原理の概念を理解する（ハッシュの競合を解決するいくつかの方法）
• 結合-検索/分離セット（最適化とパス圧縮）
• グラフ理論 位相ソート
• グラフ理論 DFS 深さ優先探索、BFS 幅優先探索
• 最短経路ダイクストラアルゴリズム、フロイドアルゴリズム、spfaアルゴリズム
• 最小全域木プリムアルゴリズム、クラスカルアルゴリズム
• その他のデータ構造、セグメント ツリー、サフィックス配列など。

クラシックアルゴリズム

• 再帰アルゴリズム（階乗、フィボナッチ、ハノイの塔問題）
• バイナリ検索
• 分割統治アルゴリズム（クイックソート、マージソート、最も近いポイントペアの問題を見つける）
• 貪欲アルゴリズム（主に区間点選択問題、区間被覆問題に使用）
• 一般的な動的計画法（LCS（最長共通部分列）、LIS（最長増加部分列）、ナップサック問題など）
• バックトラッキング アルゴリズム (古典的な 8 つのクイーンの問題、完全な順列の問題)
• 一般的なビット操作の問題 (Sword Finger Offer および LeetCode の問題を参照)
• 高速累乗アルゴリズム（高速累乗、高速行列累乗）
• kmp およびその他の文字列マッチングアルゴリズム
• その他のすべての数論アルゴリズム（ユークリッド、拡張ユークリッド、中国剰余定理など）

この記事を読んだ後には、データ構造とアルゴリズムについて十分に理解できるはずです。データ構造とアルゴリズムは密接に関連しています。データ構造は特定のアルゴリズムを実装するためのものであり、アルゴリズムはその中核的な目的です。データ構造とアルゴリズムを学習する前に、まず本やブログを参照してその機能を理解し、次にその動作原理を学習し、そして段階的に実践（データ構造や関連する質問を書く）することができます。データ構造とアルゴリズムを深く学びたい場合、理解するだけでは十分ではなく、多くのコードの練習が必要です。そしてこの道には終わりがありません。老後まで生き、学び、磨き続けましょう。

オリジナルリンク: https://mp.weixin.qq.com/s/RSZmRRihze7gllewXmh1ng