アルゴリズムたいそう

単語カード

設定全面表示

• アルゴリズム

  問題を解決したり目標を達成したりするための計算方法や処理方法のこと
• 時間計算量

  アルゴリズムを実行したときの命令の数
• 領域計算量

  アルゴリズムに使用した変数や配列の数
• オーダ記法

  入力サイズnが十分に大きい時に計算量を漸近的に評価する手段
• 多項式時間アルゴリズム

  O(n), O(n log n), O(n^2), O(n^3)のように単純な関数の計算量の漸近的評価、オーダであり、計算が可能なもの
• 指数時間アルゴリズム

  O(2^n), O(n!), O(n^n)のような計算困難であるもの
• アルゴリズムの正当性

  正しい解を得られるかの検証
• アルゴリズムの停止性

  無限ループに陥るかの検証
• 平均計算量

  入力にある分布を仮定して計算時間の期待値で評価する場合の時間計算量
• 最大時間計算量

  時間計算量の最大値であり、アルゴリズムを実行したときの最大の命令数
• トップダウン設計法

  まず大まかなアルゴリズムを考え、
  更にそれをいくつかの小さな部分に分割して各部分のアルゴリズムの設計を進め、
  最後に全体のアルゴリズムをまとめる
• 分割統治法 再帰アルゴリズム

  問題を小さな問題に分割するのはトップダウン設計法と同じ。
  その後分割された小さな問題が元の問題と同型である。
• 再帰アルゴリズム

  処理手順がそれ自身を用いて定義されているアルゴリズムのこと
• ソーティング

  与えられたn個のデータの列{a1, a2, ... , an}をある基準に従って順に並べ変えること
• 最小値選択法(直接選択法)

  データ列の最小値を選択し未整列部分の先頭に置くことを順次繰り返す
• バブルソート

  隣接する2項を比較し、a_j > a_j+1のように、
  左の項が右の項より大きければ、これらを交換する操作をデータ列の左側から右側へ操作することを順次続けることにより、
  結果的に右から順にデータの位置を確定させるアルゴリズム
• 探索

  与えられたデータの中から、目的のデータを見つけること
• ヒープ

  各節点にデータを持つ完全2分木で、かつ条件:親の持つデータはその子のデータより大きいことを満たすデータ構造
  ただし、ここでいう高さmの完全2分木とは、すべての葉の深さがm-1またはmのいずれかで、mの葉がすべて左端に寄せているとする
• 半順序集合

  集合x上の関数Rが順序関係の時、対(x, <)を順序関係(半順序関係)という
  -> Rが反射的、反対照的、推移的の時のRを<とおく
• 2分木

  各節点から出る枝が2本以下の木を2分木
• 完全2分木

  深さがmの葉が2^m個である2分木
• 高さmの完全2分木の節点の総数

  2^(m+1) -1
• 内部整列

  データを全てコンピュータの主記憶領域に格納しソートする
• 外部整列

  大規模データをディスクや磁気テープなどの補助記憶装置を用いたソーティング
• 連結グラフ

  グラフ内の任意の2頂点をつなぐ道が存在する
• 全順序集合

  順序集合(x, <)において、Xの任意の要素ｘとｙに対し、x<yまたはy<xのいずれか一方が常に成り立つ
• 計算量

  アルゴリズムの計算効率や問題の難しさを図るための尺度
• ハノイの塔

  n枚の円盤があり、規則に従ってすべての円盤を柱Aから柱Bに移動させる
  
  [n=1 -> A->B], [n>1 -> n-1枚を移動]
  1. n-1枚をA->C
  2. 残り1枚をA->B
  3. n-1枚をC->B
• ユークリッドの互除法

  2つの自然数の最大公約数を求める方法
• 挿入法

  トランプゲームのように、a_1からa_i-1までがすでに整列していると仮定し、a_iを正しい位置に挿入する方法
  a_iより大きいデータを右側に移動した後、その空き場所にa_iを挿入する
• クイックソートの計算量

  O(n log n)
• ヒープソートの計算量

  O(n log n)
• バブルソートの計算量

  O(n^2)
• 挿入法の計算量

  O(n^2)
• 最小値選択法の計算量

  O(n^2)
• 2分探索法の計算量

  O(log n)
• 自然数nの階乗を計算する再帰アルゴリズム 疑似C

  -long fact(long n) {
  __if(n == 0) return 1; // 0! = 1
  __return fact(n - 1) * n; // (n- 1)! * n
  }
• 2分探索

  一定の順序にソートされたデータに対する探索法
  
  データの中央値と求めるべきデータxを比較することにより、x の存在範囲をデータの前半か後半に絞り、同様の処理を繰り返してxを探索する。

広告

コメント