昨日までのまとめ

・誤差
打ち切り誤差…有限項で打ち切るために起きる
情報落ち…絶対値の小さな数が無視される
丸め誤差…近似値にするため誤差になる
桁落ち…絶対値の差を計算すると誤差になる
・計算量の加算
基本的に最も大きい数のみ考えればよい。
なお、2^n>n^2

・2分木探索の最大比較回数はnlog2n

・ソート
バブルソート…隣り合う要素の値を比較して大小関係が逆になれば交換
基本選択法…最小値を見つけ、先頭と交換、2番目に小さいものを見つけ、2番目のものと交換
基本挿入法…未整列要素の並びの戦闘の要素を取り出し、その要素を整列済みの要素の中のただしい位置に挿入

以上の計算量はO(n^2)

クイックソート　整列対象要素の中から適当に基準値を決めて基準値より大きい要素、小さい要素に分割、　要素数が1つになるまで繰り返し行う

計算量はO(nlog2n)、ただし、整列済みのデータに対し最小値、最大値を基準値とした場合O(n^2)

ヒープソート　木構造を使ったソート方法、高速だが非安定
計算量はO(n^2)

マージソート　データ列を分割と併合を繰り返して、1つの整列済みのデータ列をつくる
安定だが、作業領域必要
オーダーはO(n^2)

Dhrystone(ドライストーン）…サーバーＣＰＵの性能評価用ベンチマーク、ＭＩＰＳで示している
FLOPS…科学技術計算用コンピュータの性能表示に用いる、浮動小数点演算命令の実行回数

ＭＩＰＳ…ＣＰＵが1秒に実行できる命令数をM単位で示したもの
SPEC…団体の名前

アーキテクチャ、暗号、アルゴリズムあたりをもうすこしやる必要あり