[資料構造]#1資料構造、#2回帰

8424 ワード
データ構造 C テキストリンク
18年第2学期に受けた資料構造の授業を復習し、整理する.

1.資料構造


1.プログラム=データ構造+アルゴリズム

  • 資料構造:コンピュータ内のデータを整理および整理するための様々な構造(スタック、キュー、リスト、辞書、ナビゲーション構造、グラフ、ツリー...)
  • アルゴリズム:コンピュータで問題を解くステップステップ(疑似コードで表すことが多い)

    • 2.データ型&抽象データ型

  • データ型:特定のプログラミング言語によって提供されるデータ/演算の集合
  • 抽象データ型:抽象定義データ型.何だけを定義し、どのように実施するかを定義しません.

    • 3.アルゴリズム性能分析

  • 時間複雑度分析
  • 実稼働時間測定
  • アルゴリズムの複雑度分析
  • 空間複雑度分析

    • 4.序数表現


    時間・空間複雑度関数を簡単に表現するためにBig−Oマーキング法が出現した.関数の「次元」は重要なので、次元数を基準に表します.

    Big-O, Ω, θ



    ただし、プログラムを実行するときは、すべての最適、平均、および最悪の状況を考慮します.△通常、最悪の場合はそうです.

    2.在貴


    1.回帰と繰り返し

  • 再帰:アルゴリズムまたは関数が実行中に「自己」を呼び出して問題を解決するテクニック.必ず止まるところがある.

    • 2. factorial


    時間複雑度O(n),空間複雑度O(1)
    // 반복
int factorial(int n) {
    int fact = 1;
    for (int i = n; i > 0 ; i--) {
        fact *= i ;
    }
    return fact;
}
// 재귀
int factorial(int n) {
    if (n <= 1) return 1;
    else return (n * factorial(n - 1));
    // 스택에 쌓아두고 함수 호출함.
}

    3.探索バイナリ

  • 配列の配列を探索するのに有利である.
  • 中間値が同じ場合はナビゲーションが完了し、小さい場合は前のリストで再度ナビゲートし、大きい場合は後のリストで再度ナビゲートします(再ナビゲート->戻る!)

    • 時間複雑度O(logn)
    binary_search(key, low, high)
if (low <= high) {
    middle <- (low + high) / 2
    if (key == list[middle]) return middle;
    else if (key < list[middle]) 
        return binary_search(key, low, middle - 1);
    else
        return binary_search(key, middle + 1, high);

    4.フィボナッチ数列


    すでに#25で議論されている.
    本科の授業資料では,関数を複数回呼び出すので,空間の複雑さが大きくなると言うだけでスキップする.でも臨時に試験範囲が設けられていたので、気にならずスキップしてしまい、今から見ると、かっこいい授業でのコスプレにも関わってきました.

    5.ハノイの塔

  • 柱計3本.
  • 原版は一度に1つ引っ越します.
  • の小さな円板には円板を拡大することはできません.
  • 64枚の基板の大きさは異なります.
    • 高校の時に数列の問題をたくさんしましたが、面白かったです.

    最大を1つ残して、n-1個移動して、それから最大を移動して、更にn-1個移動します
    =>一般式:a n+1=2 a n+1
    =>a n=2^n-1(時間複雑度:O(2^n)
    void hanoi_tower(int n, char from, char aux, char to) {
    if (n == 1) {
        from에서 to로 원판 옮기기. (print from, to)
    } else {
        hanoi_tower(n-1, from, to, aux);
        from에 있는 한 개의 원판 to로 옮기기. (print from, to)
        hanoi_tower(n-1, aux, from, to);
    }
}
    UNIXネットワークプログラミング-クライアント/サーバプログラム設計モデル(六)
    Code Kata | day6 roman_to_num