|
テスト期間中。 |
2004年07月29日(木) |
はやそ＞
テスト期間中です。
また勉強しようと思います
また日記で（ぁ
データ構造とアルゴリズム
データ構造
☆配列☆
同一データ型の同一サイズのメモリ要素が物理的に連続して並んだ物。
宣言したサイズ分だけメモリがなければプログラムが実行できず、プログラムで予め設定したサイズ分しか使用できないため柔軟性に欠けるが、その分データが連続して並んでいるため、参照が高速に行うことができる。
☆リスト☆
データをひとまとまりにして扱う点では配列と変わらないが、データが物理的に必ずしも隣接しているとは限らない。
構造体や配列を用いて表現することになり、データとその次の要素を挿すポインタ（or添字）を一緒に格納しておく。参照する場合は、データを読み込んだ後、その次の要素を挿すポインタを辿って次のデータを読み込みに行くという形になる。
構造体を用いた場合特に、malloc関数を用いれば新しくメモリを確保することができる。つまりメモリを新たに追加することが可能で、メモリ使用効率を良くすることができるため、配列よりも柔軟性があると言える。
ただし、データは物理的に連続しているとは限らないため、配列と比べれば参照が低速になる。
☆スタック☆
データを格納する物の一つ
出口と入り口が共通しており、後から入れた物ほど先に取り出される
箱に上から物を入れていくイメージ。
一番上からしか取り出すことはできない。
（後入れ先出し ＬＩＦＯとも言う）
一次元配列やリストで表現することができる。
Push-downと呼ぶこともある。
☆キュー☆
データを格納する物の一つ
出口と入り口が別で、先に入れたほうから取り出していく
筒の上から物を入れ、下から取り出していくイメージ
先に入れた方から順番に取り出すことができる
（ＦＩＦＯとも言う）
これも一次元配列や、リストで表現することが多い。
データの整列
☆バケットソート☆
n個のデータがあったとすれば
それらを最小値から最大値までの数字を添字とするキュー群を考える
例えばa1=4 a2=1 a3=7 a4=2 というデータがあれば
1〜7までの添字を持つバケツ（キューで表現）を用意する
b1 b2 b3 b4 b5 b6 b7（とする。
a1=4なので、その値を添字とするバケツb4に入れる
a2ならb1 a3ならb7 a4ならb2へ
すると
b1 b2 b3 b4 b5 b6 b7
a2 a4 a1 a3
と格納されて、左から出していけば昇順に、右から出していけば降順に並ぶ
これはデータの最大値の大きさにメモリ使用量が依存される
例えば上のデータをa1=1000にすれば
４個のデータと１０００個のバケツを用意することになり、効率が非常に低下することになる。
メモリ使用効率はＯ(m+n)（mをデータの最大値とする） となる
使用効率というか計算速度やね
☆選択法☆
数字を左or右から順番に、最小値or最大値を選んで配置していく
15 19 20 9 16 11 3 というデータを昇順に並べるとすれば
この中の最小値を見つけるために比較をしていくと3が見つかる
これを一番左の値と入れ替える
3 19 20 9 16 11 15
その後一番左を除いた残りのデータの中で最小値を求めると
9が見つかるため、これを残りのデータの中で一番左の19と入れ替える
これを繰り返せば良い。
昇順に並べ替える時、逆に最大値を見つけて一番右に配置しても良い
降順に並べ替える時は以上と逆のことをすれば良い。
このソートの最悪時間を考えてみると
最小値かどうかは最後まで調べないとわからないので
ｎ個のデータを選択法でソートすると
１周目は(n-1)回、２周目は(n-2)回 ･･･ n-1周目は1回となるから
比較回数は合計で n(n-1)/2
入れ替え回数は最大でn-1回になる。
よって処理時間はnの2乗に比例することになる。→よってＯ(n^2)
☆挿入法☆
n個の要素のうち最初何個かが、既に整列していると考えて
そこにそれ以外の値を間に挿入していく
1 7 15 3 8 12 9 を昇順に並べる場合
1 7 15までは既に昇順なので、それ以降の値を
その間に挿入していく
3は1と7の間なのでそこに挿入して
1 3 7 15 と後残り8 12 9 となる。
こうやって残りの値を全て整列されている物の間に挿入していけば良い。
逆順に並んでいる時、つまり昇順に並べる時は降順に またはその逆に
並んでいる時、比較回数は最大になる。
その時比較回数はn(n-1)/2となり、比較回数はそれ以下である
よって全体の計算時間はＯ(n^2)となる。
☆ヒープソート☆
最小値を選択し、順番に当てはめていく。
この点では選択法と変わらないが、最小値を選択する時に
ヒープを利用する。
ヒープを構成するのにかかる時間はＯ(n)
その後最小値を見つける時間は
log(n-1)+log(n-2)+･･･log(2)=log(n-1)! <= nlognとなるから
全体の計算時間はＯ(nlogn)となる。
☆マージソート☆
与えられた１つのデータ群を２つに分けて
それぞれで整列を行うということを繰り返す
15 19 29 9 16 11 6 3 を昇順に並べる時
これを２つに分割すると
（15 19 29 9）と（16 11 6 3）という２つに分割できる
これをさらに２つに分割すると
（15 19）（29 9）（16 11）（6 3）となる
これを昇順にそれぞれ並べて
（15 19）（9 29）（11 16）（3 6）と並べ替えて、となり２つを統合
（9 15 19 29）（3 6 11 16）と並べ替えて、となり２つを統合
（3 6 9 11 15 16 19 29） 完成
全体の計算時間を考えてみる
計算時間T(n)=2T(n/2)+cn(n>=2)と表すことができる
これは数字群Ｓがあったとすれば
これに統合する元の２つ、Ａ群とＢ群を考えると
Ｓの比較回数＝（Ａの比較回数）+（Ｂの比較回数）+２つの昇順並べ替え
となる。ＡとＢの要素の数はＳの1/2だからそれぞれＴ（n/2）
Ｔ(1)=c'として漸化式を解けば
c'n+cnlognとなり、計算時間はＯ(nlogn)であるといえる
☆クイックソート☆
数値を選ぶ（できるだけ中央値が良い。この値をピボットと言う。
その選んだ要素よりも大きいものと小さいもので２つに分割する
という作業を繰り返して整列を行う。
15 29 19 11 6 9 16 3 というデータを昇順に並べる時
数字を選ぶ。 ここでは８としてみる
左から順番に基準より大きいものを
右から順番に基準より小さいものを探す。
この場合15と3が見つかる。 この２つを入れ替える
3 29 19 11 6 9 16 15 同様にしていくと
3 9 19 11 6 29 16 15
3 9 6 11 19 29 16 15 となる
ここで左３つは小さいほう 右５つは大きいほうという２つに分けて
また同じ作業を行う。
（3 9 6）で8を基準にして
（3 6）（9）ここで５を基準にして
（3）（6）（9）
（11 19 29 16 15）で18を基準にして
（11 15 16）（29 19）
･･･
（11）（15）（16）（19）（29）
あとは結合すればよい。
このピボットの値によって計算時間は大きく異なる
例えばピボットが常にデータの中の最小値を選んでいた場合
選択法とほとんど変わらない作業を行うことになるため、Ｏ(n^2)となる
それ以外、基本的には平均時間としてＯ(nlogn)となる（らしい）。
|
|
