-
アルゴリズム問題を解決したり目標を達成したりするための計算方法や処理方法のこと
-
時間計算量アルゴリズムを実行したときの命令の数
-
領域計算量アルゴリズムに使用した変数や配列の数
-
オーダ記法入力サイズ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を探索する。
ログイン
オンライン単語帳
このページを利用するにはログインする必要があります。ログインするとAnkilotをより便利にご利用いただけます。