データ構造とアルゴリズムの概要


リード
データ構造とは?異なる教材をめくると、いろいろな説明が見られます.実際、この問題はコンピュータ科学界では今まで標準的な定義がなかった.
       ,    (  :data structure)       、       (    )

問題を考える
書籍の配置
質問:もしあなたが本屋の主人であれば、どのようにあなたの本を並べて、お客様が一番早く欲しい本を見つけることができますか?
  • 方法1:
  • を勝手に置く
    本を置くのはとても便利で、新しい本が空席に直接差し込まれています.しかし、検索するのは不便で、この本がなければ、本棚全体をめくる必要があります.
  • 方法2:書名のピンインアルファベット順に
  • 排出
    新刊書の挿入は新刊書に空間を空け、図書を後ろに移動させる必要がある.
  • 方法3:本棚をいくつかのエリアに分け、各エリアにある種類の図書を指定して置く.各カテゴリにおいて、書名のピンインアルファベット順に
  • を排出する
    検索と挿入の作業量は大幅に減少していますが、各カテゴリの図書がどれだけあるかは見積もることができず、スペースの浪費を招きやすいです.
    デジタル印刷
    問題:ライトプログラムは1つの関数PrintNを実現して、1つの正の整数がNのパラメータに入るようにして、順番に1からNのすべての正の整数を印刷することができます
    //   
    function PrintN($n)
    {
        for ($i=1; $i <= $n; $i++) { 
            echo "{$i}
    "; } } // function PrintN($n) { if ($n > 0) { PrintN($n-1); echo "{$n}
    "; } }

    Nが100、1000、10000…と入力すると、Nがますます大きくなると、実装バージョン1とバージョン2の違いは何ですか?(debug_backtrace)
    いちじたこうけいさん
    質問:一元多項式の標準式は、f(x)=$a_と書くことができます.0$ + $a_1$x + ... + $a_{n-1}$$x^{n-1}$ + $a_n$$x^n$.多項式の次数nが与えられ、全体係数${a_i}^n_{i=0}$は配列a[]に格納される.この多項式の与えられた点xでの値を計算するプログラムを書いてください.
    function f($n, $a, $x)
    {
        $p = $a[0];
        for ($i=1; $i <= $n; $i++) { 
            $p += $a[$i] * pow($x, $i);
        }
        return $p;
    }
    $x = 2; $n = 1;
    $a = [];
    for ($i=0; $i <= $n; $i++) { 
        $a[$i] = $i+1;
    }
    $fn = f($n, $a, $x);
    echo $fn . "
    ";

    公因式xを提案することによって乗算の演算回数を減らし、多項式を次のように書き換える.
    f(x) = $a_0$ + x($a_1$ + x(...($a_{n-1}$ + x($a_n$))...))
    function f2($n, $a, $x)
    {
        $p = $a[$n];
        for ($i=$n; $i > 0 ; $i--) { 
            $p = $a[$i-1] + $x * $p;
        }
        return $p;
    }

    問題解決の効率
    非常に簡単な問題を解決するには、多くの方法があり、異なる方法間の効率が非常に異なる可能性があります.問題解決方法の効率は, に関係し, に関係し, にも関係している.
    『PHP面接クイズ』https://github.com/colinlet/PHP-Interview-QAstar注目を歓迎~~
    実際のPHP面接と結びつけて、自分が直面した問題や、ネット上の他の人が直面した問題をまとめ、簡潔で正確な答えを提供してみましょう.
    ネットワーク、データ構造とアルゴリズム、PHP、Web、MySQL、Redis、Linux、セキュリティ、設計モード、アーキテクチャ、面接などの部分を含む
    データ構造
    定義#テイギ#
  • データ構造の定義は、まず、図書の配置方法と同様に、コンピュータ内のデータオブジェクトの組織方式を含むべきである.また、データオブジェクトは、本棚に本を置くのは、欲しい本を見つけたり、新しく買った本を挿入したりするための一連の操作に関連しています.
  • は、データ構造を議論する際に、 自体およびコンピュータ内の に関心を持ち、それらに関連する にも関心を持ち、これらの動作を実現するための最も効率的なアルゴリズムにも関心を持っている.
  • データオブジェクトのコンピュータにおける組織方式について、2つの概念を含む:データオブジェクトセットの論理構造、データオブジェクトセットのコンピュータにおける物理記憶構造
  • .
    抽象データ型
  • 抽象データ型(Abstract Data Type)は、「抽象」である「データ構造」の記述である.データ型の説明:データ・オブジェクト・セット、データ・セットに関連付けられたアクション・セット.
  • 抽象:データ型を記述する方法は、特定の実装に依存しない.すなわち、データオブジェクト集合操作セットの記述は、データを格納する機械に関係なく、データ格納の物理構造に関係なく、実装操作のアルゴリズムおよびプログラミング言語に関係しない.抽象はコンピュータが問題を解く基本的な方法と重要な手段であり、1つの設計が多くのシーンに応用できるようにする.

  • アルゴリズム#アルゴリズム#
    定義#テイギ#
    アルゴリズム(algorithm)は9世紀のペルシャ数学者から数学的にアルゴリズムという概念を提案した.
    アルゴリズムは であり、いくつかの入力(必須ではない)を受け入れ、出力を生成し、限られたステップの後に必ず終了する.
    アルゴリズムはプログラムではなく、アルゴリズムはプログラムより抽象的で、表現が何をしているのか、細部を無視してどうするのかを強調します.このようなメリットは、全体的な考え方をわかりやすくし、モジュール化したスタイルを形成することです.
    アルゴリズム複雑度
    測定、比較アルゴリズムの指標は主に以下の2つがある.
  • 空間複雑度S(n):アルゴリズムにより作成するプログラムは、実行時にメモリセルの長さ
  • を占有する.
  • 時間複雑度T(n):アルゴリズムによるプログラムの実行時間の長さ
  • .
    解析の一般的なアルゴリズム効率:
  • 最悪状況複雑度$T_{worst}$(n)
  • 平均複雑度$T_{avg}$(n)

  • 「データ構造とアルゴリズムの概要」原文リンク:https://blog.maplemark.cn/2019/07/データ構造とアルゴリズムの概要.html