「データ構造"、"コンピュータネットワーク"、"コンピュータの構成の原則"、"オペレーティングシステム"-大学の角を曲がると、卒業後1年以上されているコンピュータの専門家の4つの主要な基本的なコースは、学習が本当にずさんであるとき、それは今、ほぼ終了している点に。"基礎がしっかりしていない、地面が揺れている"、一度怠け、今それを補う必要があります。
「図

1：データ構造の概要

データ構造

1.1、データ構造の起源

1968年、米国のドナルド・E・クヌース教授が、「The Art of Computer Programming」の第1巻「Basic Algorithms」の中で、データの論理構造と記憶構造、およびそれらの操作について、より体系的に解説し、データ構造のカリキュラムを作りました。

70年代前半になると、大規模なプログラムが登場し、ソフトウェアが比較的独立し始め、構造プログラミングがプログラミング手法の主要な内容となり、「データ構造」が注目されるようになり、「プログラミングの本質は、明確な問題に対して良い構造を選択し、良いアルゴリズムを設計することである」と考えられるようになりました。

1.2 基本概念と用語

データ：客観的な物事を記述する記号で、コンピュータで操作でき、コンピュータで認識でき、記号の集まりを処理するためにコンピュータに入力できるオブジェクト。
データ要素：データの構成要素で、何らかの重要性を持つ基本単位で、通常コンピュータでは全体として扱われます。レコードとも呼ばれます。
データ・アイテム（Data item）：データ・エレメントは複数のデータ・アイテムから構成されることがあります。
データオブジェクト：同じ性質のデータ要素の集まりで、データのサブセット。

では、データ構造とは何かということに注目してみましょう：

構造とは、分子の構造（分子を構成する原子の配置）のような、単純な関係のことです。厳密に言えば、構造とは構成要素がどのように組み合わされ、配置されているかを指します。現実の世界では、異なるデータ要素は互いに独立しているのではなく、特定の関係を持っており、これらの関係は構造と呼ばれています。

データ構造とは？

コンピュータでは、データ要素は孤立した無秩序なものではなく、本質的に結びついたデータの集まりです。データ要素間の1つ以上の特定の関係がデータの組織化です。

1.3 論理構造と物理構造

データ要素同士は1つ以上の特定の関係を持っているので、その関係が何を指すのかを見てみましょう。

データ構造は視点によって論理構造と物理構造に分けられます。

論理構造

論理構造は、データ要素間の論理的な関係を反映したもので、言い換えれば、操作対象から抽象化された数学的なモデルであるため、抽象構造とも呼ばれ、通常、データ構造は一般的に論理構造を指すと言うために使用されます。

以下に論理構造の一部を示します：

図2：コレクション構造

図3：線形構造

図4: ツリー構造

図5: グラフ構造

物理構造

物理構造とは、データがコンピュータに格納される形式のことで、ストレージ構造とも呼ばれます。データ要素の表現と関係の表現が含まれます。

データ要素の格納構造には、逐次格納と連鎖格納の 2 種類があります。

シーケンシャル・ストレージ

シーケンシャル・ストレージは、データ要素が連続したアドレスのメモリ・セルに格納される構造で、データ間の論理的および物理的な関係は同じです。

図6：シーケンシャル・ストレージ

連鎖型ストレージ

連鎖ストレージ構造は、データ要素を任意のストレージ・ユニットの集合に格納します。データ要素の格納関係は論理的な関係を反映しません。

図7：連鎖ストレージ

アルゴリズム

2.1, アルゴリズムとは？

アルゴリズムの定義から始めましょう：

平たく言えば、アルゴリズムとは、問題を解くための方法やプロセスのことです。 1つの問題は複数のアルゴリズムを使って解くことができ、あるアルゴリズムが特定の問題を解決します。

では、データ構造とアルゴリズムにはどのような関係があるのでしょうか？アルゴリズムとデータ構造は密接な関係にあります。

データ構造は、データに課されるアルゴリズム要件を理解することなしに決定することはできません。また、アルゴリズムの構造設計と選択は、そのベースとなるデータ構造に依存します。

つまり、アルゴリズムの構造は、そのベースとなるデータ構造に依存します。

コンピューティングの分野では、アルゴリズムとは本質的に、問題のニーズに従ってデータの論理構造と記憶構造に基づいて課される操作です。

データの論理構造や記憶構造は一意ではないので、アルゴリズムの記述も一意とは限りません。論理構造と記憶構造が同じであっても、アルゴリズムが一意であるとは限りません。データ構造について学ぶことで、プログラマはより良いアルゴリズムを選択することができます。

2.1 アルゴリズムの特徴

アルゴリズムには、入力、出力、無限大、決定性、実行可能性という5つの基本的な性質があります。

連鎖ストレージ

入力と出力の特性は、アルゴリズムが0以上の入力を持つことから理解しやすいものです。ほとんどのアルゴリズムでは入力パラメータが必要ですが、"hello world!"の印刷のように入力パラメータが不要な場合もあります。アルゴリズムには少なくとも1つ以上の出力があります。アルゴリズムには出力がなければならず、なければそのアルゴリズムは無意味です。

有限のステップ数を実行し、無限ループに陥ることなく自動的に終了し、許容可能な時間で各ステップを完了するアルゴリズム。現実には、無限ループを満たさないデッドループのコードが書かれることがよくあります。
決定論

アルゴリズムの各ステップには明確な意味があり、二元性はありません。アルゴリズムには、ある条件下での実行経路が1つしかなく、同じ入力には一意な出力しかありません。アルゴリズムの各ステップは曖昧さなく正確に定義されています。

決定論

アルゴリズムの各ステップが実行可能であること、すなわち各ステップを有限回実行することで完了できること。実現可能性とは、アルゴリズムが正しい結果を伴うマシン上で実行できるプログラムに変換できることを意味します。

2.2 アルゴリズム設計の要件

よく設計されたアルゴリズムは、通常、次の目標を達成するために考慮されるべきです：正しさ、可読性、堅牢性、効率性、および低いストレージ要件。

2.3 アルゴリズム分析

アルゴリズムは計算問題を解くための道具です。アルゴリズムの良し悪しは直接問題解決の効率に影響し、問題解決の効率を向上させるために、特定の問題解決の方法については、アルゴリズムの具体的な説明を考慮する必要性に加えて、また、アルゴリズムの良し悪しの尺度を持っている必要があります。

アルゴリズム分析とは、主にアルゴリズムの良し悪しを判断することであり、アルゴリズムの良し悪しを判断するには、一般的に時間的観点と空間的観点の2つの観点からアルゴリズムを測定します。一般的には、時間的な観点からのアルゴリズムの分析が多く考慮されます。もちろん、アルゴリズムの判断は良いか悪いかだけでなく、時間や空間の簡略化で測定することはできませんが、包括的な検討の実際の状況に基づいている必要があります。

アルゴリズムの測定基準は、主にこの2つの方法に基づいています：

実現可能性

この方法の欠点は、まずアルゴリズムに基づいたプログラムを実行する必要があること、また滞在時間の統計がコンピュータのソフトウェアやハードウェアなどの環境要因に依存するため、アルゴリズム自体の長所や短所が曖昧になりがちなことです。そのため、2番目の方法がよく使われます。

事後的統計手法

高水準言語で書かれたプログラムをコンピュータで実行するのにかかる時間は、以下の要因に依存します： - アルゴリズムに選択された戦略 - 問題の大きさ - プログラムが書かれた言語 - 結果として得られる機械コードの品質 - 機械による命令の実行速度機械が命令を実行する速度

もちろん、ハードウェアの方向性はさておき、アルゴリズムの効率は問題の大きさに依存します。

しかし実際には、2つのアプローチを組み合わせることが可能です。一般に、問題を解くアルゴリズムへの入力は問題サイズと呼ばれ、整数 n で表されます。例えば、行列積問題の入力は問題サイズです。例えば、行列積問題の規模は行列の次数であり、グラフ理論の問題の規模はグラフの頂点や辺の数です。

アルゴリズムの各ステップにはいくつかの文があり、頻度は各文が実行される回数です。アルゴリズムの時間複雑度は、アルゴリズムが費やした時間です。

簡単に言えば、基本単位である基本文の実行時間であり、アルゴリズムの全ての文の中で基本文の実行回数の合計がアルゴリズムの時間コストであり、アルゴリズムが解く問題の大きさnの関数です。問題サイズnが無限大になるとき、時間複雑度の次数はアルゴリズムの漸近時間複雑度と呼ばれます。

時間複雑性

アルゴリズムの時間複雑性の定義

時間の複雑さを大文字のO()で表現することをビッグO表現と呼びます。

図8：ビッグO表現

.定数オーダー

逐次構造の時間複雑度

例として以下のアルゴリズムがあります：

        int sum=0,n=100;    //1回実行する
        sum=sum+n/2;        //1回実行する
        System.out.println(sum);    //1回実行する

このアルゴリズムの実行回数の関数は、f = 3です。実行回数はnで増加しないので、このアルゴリズムの時間複雑度はO(1)です。

逐次構造だけでなく、分岐構造の場合も、真でも偽でも実行回数は一定で、nが大きくなっても変化しないので、単純な分岐構造の時間複雑度もO(1)です。

線形順序 .

線形順序のループ構造はもっと複雑です。アルゴリズムの順序を決定するには、多くの場合、特定のステートメントまたはステートメントのセットが実行される回数を決定する必要があります。したがって、アルゴリズムの複雑さを分析する鍵は、ループ構造の動作を分析することです。

        for(int i=0;i<n;i++){
            //時間複雑性を持つ操作
            System.out.println(n);
        }

上記のアルゴリズムでは、アルゴリズムがn回実行されるので、時間の複雑さはO(n)です。

2.3.1.3、対数順序

次のアルゴリズムを見てください。一見したところ、時間複雑度はO(n)です。

        int n=10;
        int count=1;
        while (count<n){
            count=count*2;
            //時間複雑性を持つ操作
            System.out.println(count);
        }

つまり、log2^n回ループを抜けます。言い換えれば、ループはlog2^n回後に終了するので、このループの時間複雑度はO(logn)です。

正方形の順序 .

O(n)コードを再びネストした次の二重ループを見てください。これはm*n回実行され、時間複雑度はO(n²)です。

        for (int i=0;i<n;i++){
            for (int j=0;i<m;j++){
                //時間複雑性を持つ操作
                System.out.println(i*j);
            }
        }

2乗次数を発展させると、3乗次数O(n³)、k次数O(n^k)もよく理解されており、3レベルのループとkレベルのループがあります。

2.3.2, 空間の複雑さ

空間の複雑さとは、アルゴリズムが動作中に一時的に占有する記憶領域の量を表すもので、やはり傾向を反映し、S(n)で定義されます。

S(n) = O(f(n))

一般に、プログラムがマシンで実行される場合、プログラム自体の命令、定数、変数、入力データの格納に加えて、データ操作のための記憶装置も必要になります。入力データが占有する空間が問題そのものにのみ依存し、アルゴリズムに依存しない場合は、アルゴリズムの実行に必要な補助ユニットを分析すれば十分です。アルゴリズムの実行に必要な補助空間が入力データSに対して定数である場合、アルゴリズムはO(1)の空間複雑度でその場で動作すると言われます。

通常、「時間の複雑さ」という用語は、実行時間の要件を指すために使用され、「空間の複雑さ」は、空間の要件を指すために使用されます。複雑さ」が修飾語なしで使われる場合、通常は時間の複雑さを指します。

この記事は、以下の主な情報源を用いた学習ノートタイプのブログです！

1: Deng Junhui, ed. データ構造とアルゴリズム 2: 王世民他編. データ構造とアルゴリズム解析 3: マイケル・T・グッドリッチ他編.Javaにおけるデータ構造とアルゴリズム-第6版 4: Yan Weimin, Wu Weimin, editors . データ構造 5: Jie Cheng . データ構造大全 6:7:.

データ構造を学び直す