[TIL 210602]資料構造#1


データ構造バー


メモリスペース+演算(読み取り、書き込み、挿入、削除、ナビゲーションなど)
資料構造では,有限回数の演算を入力して正解を出力する過程がアルゴリズムである.

データ構造の例

  • 変数(変数):a=5(→書き込み操作)、print(5)(→読み取り操作)
  • 配列、リスト...
  • アルゴリズムの時間的複雑さ


    →仮想マシン(RAM=CPU+メモリ+基本演算)+仮想言語(ダミー言語)+仮想コード(ダミーコード)
    ≪基本演算|Basic Operations|oraolap≫:単位時間で実行される演算の集合.たとえば、割当て/借用/コピー、算術、比較、論理、ビット演算などです.
    仮想言語:基本演算、比較(if/ifelse...)、反復可能(for while)、関数(定義/呼び出し/戻り)などの仮想言語
    仮想コード:アルゴリズムを実装する仮想コード
    時間複雑度T(n)=アルゴリズムが最悪入力を実行する時間
    Big-O符号O(n)=T(n)におけるn→∞の場合、成長率を決定するnの最大次項(n、n^2、log(n)等)

    配列とリスト


    ▶配列とリストが基本的な順序付け資料構造
    1.C言語の配列
    int A[4] = {2,4,0,5}
    →Aに割り当てられたメモリにそれぞれ値を格納する.
    よって、A[2]のアドレス=A[0]のアドレス+2*4 byte
    →値を追加するにはmallocにメモリを割り当てる必要があります
    2.Pythonのリスト
    A = [2,4,0,5]
    →Aの各インデックスは,オブジェクト(2,4,0,5)のアドレスをそれぞれ指定する.
    →容量自動調整可能(動的配列)、append、insert、pop、removeなどの方法を提供

    シーケンスデータ構造のタイプ


    1.並べ替え、リスト
    →indexから任意の要素にアクセス可能
    注意)append,popの時間的複雑度=O(1)/insert,removeの時間的複雑度=O(n)
    2. Stack, Queue, Dequeue
    →限られたアクセスのみ許可(挿入、削除)
    Stack → LIFO
    Queue → FIFO
    Dequeue → Stack + Queue
    3.接続リスト
    →不連続空間に格納された資料構造
    したがって、自分の値アドレスと次の値のアドレスを一緒に保存し、リンクを最初から追跡してアクセスする必要があります.