アルゴリズムとデータ構造
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
* アルゴリズムとデータ構造 [#p8c4a8bb]
この頁の解説貧弱すぎｗｗなめてんだろｗｗｗ~
と思った奴は何か書いてくれ
#contents
* 計算量 [#p6073ad2]
アルゴリズムがどれだけ効率的かを示す概念が''計算量''です...
具体的に、下に述べている[[線形探索>#oc5e463b]]の例で計算...
一般に、計算量がデータ数によらない定数（O(1)と書きます）...
なお、このような記法はあくまでnが大きい時に重要になるので...
* アルゴリズム [#v958b98c]
問題を解くための手順を''アルゴリズム''と呼ぶ。~
但し、アルゴリズムと呼ばれるためには以下の条件を満たさな...
・問題を解く上で正しいこと。
・手順が具体的に示されていること。
つまり、コンピュータで実行可能なように、曖昧さがなく記...
・有限の実行時間で、必ず終了すること。
** 探索 [#i297b629]
*** 線形探索 [#oc5e463b]
英語ではリニアサーチ。~
何のひねりもなく、先頭から末尾まで探していくだけのサーチ...
データが多くなると遅くなりがちですが、何の前提条件も無く...
シンプルなので、要素の数が10個前後の小規模な配列に対して...
例:C言語(配列のアドレスとサイズを渡し、numと一致する要素...
int linear_search(int *array, unsigned int size, int num...
int i;
for(i = 0; i < size; i++){
if(array[i] == num) return i;
}
return -1;
}
配列の要素数が増えれば増えただけ探索に時間がかかるように...
要素数10000の配列は、要素数10の配列の1000倍時間がかかるわ...
このように、データ量と処理時間が単純に比例して増える事を...
１番時間がかかるのは探しているデータが存在しない場合で、...
*** 二分探索 [#qce356fb]
英語ではバイナリサーチ。~
整列済みの要素群に対して実行します。 性質上、再帰を用い...
例:C言語(配列のアドレスとサイズを渡し、numと一致する要素...
int binarysearch(int * array , unsigned int size , int n...
int begin = 0; int end = size - 1; int center;
while(1) { //無限ループ
center = (begin + end) / 2;
if(array[center] >= num) { //num...
if(array[center] == num) { return center; ...
end = center - 1;
}
else { //num...
begin = center + 1;
}
if(begin > end) return -1; //探す範...
}
}
整列の中央と探索対象を比較すると、その結果で整列の
左側あるいは右側だけに候補を絞ることができます。~
そして、その搾られた候補に対して同じ要領で中央の値との比...
いずれある時の中央の値あるいはただひとつに絞られた候補と...
探索対象が現れます(整列に探索対象があれば)
要素数１の時の処理時間を基準にすると、要素数４でも３倍、...
１回の比較で、探索候補の半分を振るい落とせるためです。~
このように、データ量が倍に増えても処理時間は緩やかにしか...
線形探索のO(n)と比べるとデータ量の増加に強いものの、処理...
要素が少ないうちは線形探索よりも遅かったりしますが、総合...
** 整列 [#h84db045]
*** ボゴソート [#h92fd60b]
世間にはあまり知られておらず、専門書にもまず載っていない...
他のソートアルゴリズムに比べ極めて分かり易いアルゴリズム...
訓練をすれば猿はおろか犬でも習得できる。~
要素をランダムに並べ替え、順番に並んでるかを確認し、もう...
この操作をソートが完了するまで行う。~
運がよかったら一発で終了するがそうでない場面の方が圧倒的...
ソートが終了するかかどうかは「無限の猿定理」でぐぐると幸...
~
所謂ツンデレソート。「一回で終わるわよこんなソート！」~
一回で終わったためしがなく、バブルソートよりはるかに遅い。~
計算時間はO(n*n!)~
void swap(int* p1, int* p2)
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
void bogo_sort(int* array, int size)
{
srand((unsigned)time(NULL));
int i;
while(1){
int sort_flag = 0;
for(i = 0; i < size-1; i++){
if(array[i] > array[i+1]){
sort_flag = 1;
}
}
if(sort_flag){
int t1 = rand()%size;
int t2 = rand()%size;
swap(&array[t1], &array[t2]);
}
else{
return;
}
}
}
~
***バブルソート [#c164d24f]
初心者の坊や達を優しくソートの世界に導いてくれる方。~
とても素直だけど、遅いので実戦の場に出ず教育者として活躍...
例:C言語
void bubble_sort(int *array, unsigned int size){
int i, j, t;
for(i = 0; i < size; i++){
for(j = size - 1; j > i; j--){
if (array[j] < array[j - 1]){
t = array[j];
array[j] = array[j - 1];
array[j - 1] = t;
}
}
}
}
隣り合ってる要素を比べて、並べたい順番になってなかったら...
要素が正しい位置に泡のように登っていくのでバブルソートと...
単純ですが無駄な比較が多く、遅いです。
サンプルコードを見れば分かるように、ループを二重に回して...
***シェーカーソート [#eaad47d0]
バブルソートの親戚。~
挟みこむような動きで少しだけ無駄を減らす事に成功しました。~
カクテルソート等とも呼ばれます。 オシャレですね。~
バブルソートで走査中、最後に入れ替えがあった位置よりも後...
つまり、最後に入れ替えがあった位置を記録し、次からはそれ...
そこで更に、前方後方と交互に走査すれば、両方から範囲を狭...
%%ぶっちゃけ大して変わらないとか言うな。%%
実際計算量もO(n^2)。
***コムソート [#d6da5661]
バブルソートの親戚。~
色々な大きさの櫛を駆使します。~
隣同士ではなく、まず適当に大きな間隔を開けて比較・交換を...
どんどん間隔を小さくしていきつつ走査を繰り返し、最後は間...
この隣同士の交換が終わった時、既にちゃんと整列出来てしま...
ずっと細かく見ていくよりも、最初は大雑把にやった方が効率...
飛び飛びに揃えていくのが髪をとかす櫛（コム）のように見え...
計算量は理論的にはO(n^2)のはずですが、実験的にO(n log n)...
***挿入ソート [#b78ed62f]
手当たり次第に突っ込む単純な子ですが、状況次第ではなかな...
大変に開放的な性格です。~
例:C言語~
void insertion_sort(int *array, unsigned int size){
for (i = 1; i <size ; i++) {
for (j = i; j > 0 && array[j-1] > array[j] ; j--)
{swap(data[j-1] , data[j]); } //要素の交換
}
前から順に見ていき、要素を正しい位置に挿入していきます。~
この「挿入」の操作そのものは、バブルソートと同じような要...
動きとしては、配列の前部に 整列したデータがどんどん溜まっ...
ほとんど整列済みのデータなら離れた所まで挿入する事が少な...
計算量はO(n^2)ですが、そのような性質から、O(n log n)のソ...
*** シェルソート [#ua3da88b]
挿入ソートの親戚。~
やはり突っ込むばかりだけれど、少しずつ間隔を開けたりする...
別に貝殻が好きというわけではなく、Shellさんが開発しただけ...
挿入ソートとシェルソートの関係は、バブルソートとコムソー...
「最初は大雑把にやって、最後だけ細かく仕上げた方が効率が...
具体的には、ある程度の間隔を開けて挿入ソートを行い、どん...
*** 選択ソート [#t69c50e9]
馬鹿ソートとか言われたりするけど気にしない明るい子。~
とりあえず一番小さいのを探し続ければそのうち揃うよね！
配列を走査し、最も小さい(ソート後に端に来る)データを見つ...
そして、２番目の小さいデータ、３番目に小さいデータ、と次...
最後の１個を見るまで「一番小さい」かどうかはわからないた...
交換回数は少ないため、バブルソートよりは高速と言えます。
でも計算量はO(n^2)。
*** クイックソート [#h788cb12]
最速の名をほしいままにしているが、たまにさぼっちゃう気ま...
スレンダーな子です~
複雑と思われがちですが、実は意外と単純です。~
まず配列からある要素A（''ピボット''といいます）を取り出し...
次にAより前に振り分けられた部分からまた、ある要素Bを取り...
このようにある要素をピボットとして取り出し、それを基準と...
計算量は分割の回数が大体O(log n)、各ステップ毎にO(n)かか...
このように効率の悪いピボットを選ぶ可能性を排除するため、...
クイックソートの重要な欠点としては、他に不安定であること...
void sort(int*a,int s){
int i=-1,j=s,p=a[s/2],t;
for(;;){
while(a[++i]<p);
while(a[--j]>p);
if(i>=j)break;
t=a[i];
a[i]=a[j];
a[j]=t;
}
if(0<i-1)sort(a,i);
if(j+1<s)sort(a+j+1,s-j-1);
}
*** マージソート [#y34cbfeb]
いつも手を抜くことなく、速さを常に追求する努力家~
クイックソートには負け越しているのをくやしがっている~
他の子より大きいのが悩み~
まず、配列を真っ二つに分けます。 分かれて出来た２つの配...
これを繰り返し、完全にバラバラになってしまうまで分割して...
分割が終わったら、今度は逆にマージ(合併)していきます。 ...
マージして出来た配列を更にマージしていって、最後にたった...
綺麗に並んだ配列２つをマージする時は、それぞれの配列の「...
（１，４，５）と（２，３，６）なら、まず左端の１と２だけ...
マージにO(n)の余分なメモリ領域が必要な事と、平均するとク...
それだけじゃクイックソート使えばいいじゃないかとなります...
外部記憶が必要なくらい大きなソートをする場合クイックソー...
また、安定ソートでもあります。 なんとなく堅牢なイメージ...
*** ヒープソート [#l50b875a]
[[ヒープ>#v35e1d11]]構造を利用したソート。計算量はO(n log...
*** バケットソート [#b490822c]
他にもビンソートとか色々あだ名がある。~
趣味で大量にバケツを集めすぎて家を崩壊させてしまうような...
秘めたポテンシャルを発揮出来ずにいる。
「０～１００点のテストの点数をソートするんなら、１０１個...
という事をマジでやるというトンでもなく豪快なソートです。~
比較と入れ替えを繰り返すものが多いソートの中で、非常に独...
まず、データがいくら増えようと「バケツに入れる」という操...
（データ量が千倍になればクイックソートでも大体１万倍重く...
非常に速いソートですが、当然弱点があり「バケツを用意する...
例に出した0～100の範囲ならまだいいのですが、32bitのint型...
範囲は-2,147,483,648～2,147,483,647という事で、4294967296...
また、ソートしたいデータに同じ数値が重複してる場合があり...
バケツは単純な配列として用意する事は出来ません。配列には...
大抵はリンクリストの配列みたいな実装になるのですが、リン...
このように、使うための条件は厳しいものの、計算量は通常の...
*** 分布数えソート [#r779f37a]
バケットソートの親戚。~
一応バケットソートよりはマシなものの、やはり家が崩壊しが...
バケットソートはリンクリストを使った実装だと 動的なメモリ...
なので、もっと上手い方法は無いのか、という事で考え出され...
まず、以下のようなデータがあったとします。
0 1 2 0 0 3 1 2 0 2 2 0
これを昇順にソートすると
0 0 0 0 0 1 1 2 2 2 2 3
このようになるわけですが、最も左を「0番目」として数えると~
0は0番目から、1は「0の個数(5)」である5番目から、2は「0の...
3は「0の個数(5)＋1の個数(2)+2の個数(4)」である11番目から...
これを利用し「何番目から始まるか」という数だけをバケツに...
同じ数値が重複してても、その要素を処理するたびに「何番目...
このような実装をすれば リンクリストのための余分なメモリも...
ただし、要素の数を数えるための走査と 実際にソートをするた...
ソートしようとしているデータの規模によってはかえって低速...
(リンクリスト用のメモリの動的確保や分岐は結構重いので、測...
*** 基数ソート [#od200194]
バケットソートの友人。 英語にするとラディックスソート。~
極限られた状況でのみ他を圧倒する速さを出す可能性を秘めて...
しかし、あまり活躍の機会がないのでたまに忘れ去られてたり...
基数というのは数を表す際に基本となるまとまりの事で、例え...
１桁目、２桁目、３桁目のように桁ごとにソートしても、順番...
以下のようなデータがあったとします。
19 70 35 48 24 14 40
これを１桁目だけに注目して、小さい方を左に来るようにソー...
70 40 14 24 35 48 19
更に、この順番をなるべく保ったまま２桁目だけに注目してソ...
14 19 24 35 40 48 70
このように、結果的に綺麗に揃っており、これは3桁に増えよう...
例えば、バケットソートで0～9999の範囲を整列せねばならなく...
これを利用して「下２桁を基準にソート→上２桁を基準にソート...
当然、分けただけソートの回数は増えますし、分ける事そのも...
バケットソートほどの速度は出ないのですが、それでも十分速...
速度を求めるなら割り算や剰余ではなく、CPU的にキリの良い２...
「桁ごとに区切っても揃う」という原理は別にバケットソート...
その他のソートだと単に処理の回数を増やすだけで何の利点も...
「バケットソートは超速いけど、メモリ喰いすぎるのがちょっ...
範囲さえある程度絞れるならクイックソートよりも普通に高速...
工夫次第で負の数を含んでたり浮動小数を扱ったりする場合に...
*** 逆写像ソート [#pfbe4b79]
バケットソートの親戚。~
一見、数学的で難解な事を考えていそうな雰囲気ですが、割と...
写像とは小難しそうな数学用語ですが、「２つの数字の集まり...
添字を入れると要素が出てくる配列も 添字→要素の写像と言え...
「逆写像」というと、その逆になり、要素→添字という写像にな...
そういう配列＝バケツと考えると、実の所それはただのバケッ...
バケットソートとの違いは「値が同じ要素があった時の対処」...
その対処の仕方とは「添字をポインタ代わりに使ってリンクリ...
リンクリストでいう next に対応する添字の値を確保するため...
この配列のおかげで、バケツに１つの要素しか入れる必要が無...
ぶっちゃけバケットソートや分布数えソートを使えば済むので...
*** 奇遇転置ソート [#f9f10dce]
バブルソートの親戚。~
チームプレーや流れ作業が得意な方。
バブルソートは隣合った要素を比較、交換していくので~
「１ ２」「２ ３」「３ ４」を添字として処理していくわ...
奇遇転置ソートは「１ ２」「３ ４」「５ ６」のような「...
「２ ３」「４ ５」「６ ７」のような「偶数 奇数」要素...
処理の回数そのものはバブルソートと大して変わらないのですが~
ポイントは「１ ２」「２ ３」 だと「２」が かぶってます...
つまり１回１回の処理が独立しているため、複数のCPUを使って...
いくら大量にCPUがあっても、走っているスレッドが１つだけな...
CPUを増やせば増やしただけ速く出来るという限界の高さに並列...
逆に言えば、並列処理が出来る環境でなければ大して役に立た...
*** シェアソート [#ya8737c6]
共有のソート。~
部下を団結させ、隊列を整えるチームワークを発揮させるやり...
一次元の住人が多いソート業界では珍しい二次元の世界の住人...
まずは、要素数[30]の配列→[6][5]の二次元配列、みたいな感じ...
そして１行目[1][i] ２行目[2][i] ３行目[3][i]……のように...
１列目[i][1] ２列目[i][2]……のように各列別々にソートする...
各行や列は、それぞれ独立しているので、並列に処理が出来ま...
「奇数行は左が小さくなるように、偶数行は、右が小さくなる...
「列は、上が小さくなるようにソート」~
これを交互に繰り返す事で、小さい値は左右にクネクネ動きな...
ちなみに、各行に対して行うソートは何を使ってもいいですが~
奇遇転置ソートやマージソート等を使うと並列性を更に上げら...
複数のCPUを搭載している状態なら、かなりの速度向上が期待出...
もちろん、並列処理が出来る環境でなければ、さほどのスピー...
*** バイトニックソート [#ud51908c]
究極のスピードを誇っているものの、力を出しすぎると地球が...
が・・・あ・・・離れろ・・・死にたくなかったら早く俺から...
理論上最高の速度が出るソートですが、やってる事は凄く単純で~
if や else等の分岐を大量に使って最小限の回数の比較、交換...
性質上、ソートする配列のサイズがわかってて、しかも極端に...
要素の数が４つだけの場合でも使うifやelseの数は数十個に及...
書くのが異様に面倒なので、実際に使いたいなら そういうコー...
また、当然実行ファイルのサイズも爆発的に増えていきます。 ~
何億回もソートを繰り返すような処理が必要でなければコスト...
※どうやら上記のソートは本来の(？)バイ・トニックソートとは...
本格的なバイ・トニックソートは、むしろマージソートに近...
正確な情報はちょっと持ってないので、知ってる人は編集し...
*** 安定ソートと、そうでないソート [#h37e2e26]
等価なデータの順番がソート前と同じという事が保証されてい...
言葉にすると難しいですので例を出しましょう。
例えば、このようなデータがあるとします。~
データ 「A：50」「B：20」「C：80」「D：20」「E：60」
これを「数字だけを基準に、小さい方が左に来るようにソート...
結果１ 「B：20」「D：20」「A：50」「E：60」「C：80」
結果２ 「D：20」「B：20」「A：50」「E：60」「C：80」
このどちらかになる事が予想出来ますが~
安定ソートだと「元々Bの方が左にあった」という事で、必ず結...
クイックソート等の安定でないソートを用いると、結果１にな...
「そんなのどうでもいいから速いほうがいいよ」という場合に...
多くのソートが安定ですが~
コムソート シェルソートなどの間隔を開けて処理をするソー...
クイックソート等は、安定でないソートとして知られています。
安定と言われているソートでも、実装の仕方によっては安定で...
あえて安定にしない事で得するような事はあまり無いです。~
また、基数ソートのように安定なバケットソートを利用しない...
** 最短経路問題 [#lf212c0c]
*** ワーシャル・フロイト法 [#f8c41450]
こいつはなぁ、全通り調べるんだよ
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
for(k = 0; k < n; k++){
if(array[j][k] > array[j][i]+array[i][k]){
array[j][k] = array[j][i]+array[i][k];
}
}
}
}
jからkに行くまでのコストについて比較してる
j→kとj→i→kっていくのがどっちが安いのか
こうすると自然に最短経路が埋まる
3重ループは全通り調べられるから他のアルゴリズムにも使える
このアルゴリズムは要素が多いときは不向き
*** ダイクストラ法 [#l7e4f36c]
ダイクストラとは、かの有名な論文''"Go To Statement Consid...
難しそうに見えて実は簡単・・・じゃないか
じゃあこの問題があったとしよう
夏休みにニートのvipeerは旅行に行こうとしましたが働いてい...
親から金をもらいに行く勇気のなかったvipperは極力少ないお...
ここで出発地から目的地まで行く最低のコストを求めよ
また、要素の数nは10まで、nが入力されたあとa b cが入力さ...
最後の行にs,gは入力されsは出発地、gは目的地である。
またbからaにも同じだけの値段がかかるとし、a,bはnまでの数...
こんなもんワーシャルフロイドでやれや(笑)って言わないでね
入力のところは
#include<stdio.h>
#define MAX (10)
int main(void)
{
int n;
int a, b, c;
int i;
int cost[MAX][MAX]; // それぞれの場所までの値段
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d %d %d", &a, &b, &c);
cost[a][b] = c; // aからbに行くまでの値段
cost[b][a] = c; // bからaに行くまでの値段
}
return 0;
}
これが基本
ここからダイクストラを実装すると
for(i = 0; i < n; i++){
used[i] = 0; // すべて使っていないことにする
val[i] = INT_MAX; // すべてのコストを最大にする
}
val[s] = 0; // 出発地のコストは0
while(1){
minVal = INT_MAX;
for(i = 0; i < n; i++){
// 確認してないで 一番安い出発地からのコストが一番安...
if(used[i] == 0 && val[i] < minVal){
minVal = val[i];
min = i;
}
}
// もしすべて確認が終わったとき終了する
if(minVal == INT_MAX){
break;
}
used[min] = 1; // 使用済みにする
for(i = 0; i < n; i++){
// minからiにいけてかつ最小コストの時更新
if(cost[min][i] && cost[min][i] + val[min] < val[i]){
// minからiまで行く値段と出発地からminにくるまでの...
val[i] = cost[min][i] + val[min];
}
}
}
こうなる
時間がないからまた今度書く
全体は
#include<stdio.h>
#include<limits.h>
#define MAX (10)
int main(void)
{
int n;
int a, b, c;
int s, g;
int i, j;
int cost[MAX][MAX]; // それぞれの場所までの値段
int used[MAX]; // 確認済かどうかのフラグ
int val[MAX]; // 出発地からのコスト
int minVal, min;
scanf("%d", &n);
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
cost[i][j] = 0; // 初期化しておく
}
}
for(i = 0; i < n; i++){
scanf("%d %d %d", &a, &b, &c);
cost[a][b] = c; // aからbに行くまでの値段
cost[b][a] = c; // bからaに行くまでの値段
}
scanf("%d %d", &s, &g);
for(i = 0; i < n; i++){
used[i] = 0; // すべて使っていないことにする
val[i] = INT_MAX; // すべてのコストを最大にする
}
val[s] = 0; // 出発地のコストは0
while(1){
minVal = INT_MAX;
for(i = 0; i < n; i++){
// 確認してないで 一番安い出発地からのコストが一番...
if(used[i] == 0 && val[i] < minVal){
minVal = val[i];
min = i;
}
}
// もしすべて確認が終わったとき終了する
if(minVal == INT_MAX){
break;
}
used[min] = 1; // 使用済みにする
for(i = 0; i < n; i++){
// minからiにいけてかつ最小コストの時更新
if(cost[min][i] && cost[min][i] + val[min] < val[i...
// minからiまで行く値段と出発地からminにくるまで...
val[i] = cost[min][i] + val[min];
}
}
}
printf("%d\n", val[g]);
return 0;
}
*** A* [#g531e457]
A*と書いて「エースター」と読む。~
ダイクストラ法は「出発地から経由地までのコスト」が最小と...
A*はこれに加えて「経由地から目的地までのコスト」も参照す...
そして、それぞれのコストの和が最小となるように次の経由地...
ただし、このアルゴリズムの適用にあたって注意がある。~
それぞれの経由地から目的地までのコストが分かっていないと...
と言っても、正確なコストはこれから調べるんだから分かるわ...
そこで、「たぶんこれくらいのコストだろう」という値を用い...
この時のコストの見積もりは、実際のコストより「必ず」低く...
証明は省略するが、最短経路を求める条件として必要だからだ。~
そのような見積りとしては、例えば目的地までの直線距離なん...
** 動的計画法 [#se794f0d]
* データ構造 [#wc0c038f]
** 配列 [#p0a42e9d]
気にしたことないだろうけど、配列も立派なデータ構造なんだ...
重要なことは、多くの言語やその処理系でO(1)のアクセススピ...
つまり、ほかのデータ構造に比べて単純な分、早いんだなこれ...
馬鹿とはさみは使いようってやつだな。
** スタック [#e04037cc]
お菓子でいうとPEZ(ペッツ)
「干し草の山」の意。~
名前の通り、新しいデータを上に積み上げていき、下に埋もれ...
上のデータを先に取り出さなければならない後入先出(あといれ...
「古いデータは取っておき、新しいデータに対して色々な処理...
例えば関数・メソッドの呼び出しの際に使われるコールスタッ...
ローカル変数は他の関数を呼び出してから戻ってくるまでずっ...
** キュー [#x9b212e8]
ところてんだよところてん
「待ち行列」の意。
名前の通り、古いデータは新しいデータの後ろに並び、新しい...
先入先出(さきいれさきだし)の構造です。~
「先のデータの処理が終わるまで、後から来たデータにちょっ...
サーバーなんかは、すぐに処理出来ない大量のリクエストが来...
(優先度が高いリクエストはキューで待たせず割り込ませてあげ...
mallocとか使わないクズキュー~
#define QMAX 100
typedef struct{
int que[QMAX];
int hp,tp;
}queue;
void init(queue* q)
{
q->hp = 0;
q->tp = 0;
}
int isempty(queue q)
{
return q.hp==q.tp;
}
void push(queue* q,int n)
{
q->que[q->tp++]=n;
if(q->tp==QMAX)q->tp=0;
}
int pop(queue* q)
{
int res=q->que[q->hp++];
if(q->hp==QMAX)q->hp=0;
return res;
}
こんな感じで使う~
http://ideone.com/Dt13X
** デック [#gffe4778]
Deque。 スタックとキューを合わせたような機能を持っていま...
具体的には「前から入れる」「前から出す」「後から入れる」...
長所：両端へのデータ挿入がO(1) 添字アクセス可能~
短所：要素の中央の挿入、削除が遅い
削除、挿入は平均すると動的配列より優れるが、単純なアクセ...
** リスト [#n30cdd26]
連結リストとも呼ばれる非常に一般的なデータ構造の一種。~
ある箱を仮想的に考え、それと別のはことをつなぐようなイメ...
箱は変数を表すと考えれば、箱同士のつなぎ方によっていくつ...
多くの言語では、箱と連結部分を一括して扱うために、構造体...
最近のモダンな言語ではライブラリにリスト構造があらかじめ...
また、Lispなど「リスト構造ありき」で言語設計がなされてい...
似たようなデータ構造に配列が存在するが、N番目の要素にアク...
従って、使用できるメモリーの割合や扱うデータの特性によっ...
リストが有利なのは、極めてデータ数が大きい際に、頻繁に途...
*** 単方向リスト [#c3b02503]
リストの要素同士を連結するとき、A→B→C→……のように、一方向...
このとき、例えばある要素を検索したい場合、現在の位置をAと...
通常、リストといえばこちらを指す。~
一方向への連結しかみないので管理が楽で、使用する領域も少...
電話帳のように、前の要素に戻る必要が生じにくいデータの表...
*** 双方向リスト [#sf7d12f5]
単方向リストと異なり、逆順にも辿れるようにしたリスト。~
単方向リスト同様、矢印表記を用いれば、A⇋B⇋C⇋D⇋……と表すこ...
特徴は、ある要素Nへのアクセスオーダが必ずしもO(N)にならな...
現在位置を覚えておきつつ、前後の要素にアクセスするような...
*** 循環リスト [#wbdee299]
上記二つのリストのどちらとも併用できる連結方法で、リスト...
通常、リストの末尾の次の要素は、NULL等の末端であることを...
例えば、あるデータを検索するときに、末尾まで検索したら先...
** 木 [#j0b14123]
上記で色々解説されてる配列・スタック・キュー・リストなど...
一方で、木構造というのは枝分かれのあるデータ構造だ。一つ...
ただし、大抵の場合、図示するときは木みたいに下から上に生...
木構造で有名なのは、ファイルシステムだ。WindowsならCドラ...
後はXMLとかJSONとかも一種の木構造だし、ドメイン名の集合な...
ここからしばらく木構造に関して解説を加えよう。木構造の解...
- ノード（節） 木構造を構成する基本単位。0個又は1個の親...
- ルート（根） 木構造の一番根本にあるノード。任意の子ノ...
- リーフ（葉） ルートとは逆に、木構造の一番末端にあるノ...
- エッジ（辺） 親ノードと子ノードを結ぶ線。~
- 先祖ノード 任意の子ノードから辿って、ルートに辿り着く...
- 子孫ノード 任意の親ノードから、子ノードを辿って到達す...
- 深さ 任意のノードのルートまでのエッジの本数。ルートの...
- 高さ 任意のノードから一番深い子孫リーフまでのエッジの...
*** 二分木 [#d6d2cafb]
木構造のうち、子ノードの数が2個以下のものを2分木という。...
二分探索と相性が良く、実装が簡単なため良く利用される。~
以下で紹介するAVL木、赤黒木、ヒープは全て二分木の実装だ。~
*** AVL木 [#l4384105]
単純な二分木の構成だと、値を挿入する順番によっては単なる...
そうなると、探索・挿入・削除の計算量がO(n)になってしまう...
平衡二分探索木は、ノードの左右の深さがほぼ等しい二分木を...
平衡二分探索木の探索のコストはO(log n)になる。~
AVLは平衡二分探索木のなかでも、厳密な平衡性を保つアルゴリ...
厳密な平衡性を保つためには、ツリーに偏りが生じた場合、回...
*** 赤黒木 [#x3cd9897]
赤黒木はあまり厳密に平衡性を保たない平衡二分探索木だ。具...
したがって、AVL木と比べると探索にかかるコストは大きい。~
一方で、赤黒木は挿入・削除時の回転の回数を減らすことがで...
赤黒木は動的なデータ構造、AVLは静的なデータ構造といった風...
*** ヒープ [#v35e1d11]
** グラフ [#f9136e1b]
*** 隣接行列表現 [#qbdd8249]
*** 隣接リスト表現 [#k4751445]
** ハッシュ表 [#f7c93b36]
*** 連鎖法 [#l66cfcc0]
*** オープンアドレス法 [#e44025a1]
*その他 [#bbfb5391]
**最大公約数(GCD: greatest common divisor) [#i9b377e0]
(ユークリッドの互除法)~
紀元前300年頃には既に存在した、最古のアルゴリズム。~
例 a0 = 497,a1 = 284とおく。
497 = 284 + a2 a2 = 213
284 = 213 + a3 a3 = 71
213 = 71 * 3 + a4 a4 = 0
つまり、497と284の最大公約数は71となる。
この計算手法をユークリッドの互除法と呼ぶ。
実装例:C言語
#include <stdio.h>
int gcd(int a0, int a1)
{
int a, b, tmp;
a = a0; b = a1;
while (b != 0) {
tmp = a % b; a = b; b = tmp;
}
return a;
}
上記GCD関数用のテストコード
int main(void)
{
int a0, a1, tmp;
printf("一番目の整数を入力してね >> ");
scanf("%d", &a0);
printf("二番目の整数を入力してね >> ");
scanf("%d", &a1);
if (a0 <= 0 || a1 <= 0) {
printf("0以下の数なんか入力すんなｗｗｗ : %d, %d...
exit(-1); // 異常終了
}
if (a0 < a1) { // 関数GCDではa0 > a1と仮定しているの...
tmp = a0; a0 = a1; a1 = tmp;
}
printf("%d と %d の最大公約数(GCD) = %d\n", a0, a1, ...
return 0;
}
** 参考リンク [#d212128a]
-[[C言語による最新アルゴリズム事典(Vevtor)>http://www.vec...
『C言語による最新アルゴリズム事典』全ソースコード~
-[[アルゴリズム演習300題(Vector)>http://www.vector.co.jp/...
「アルゴリズム演習３００題」（日刊工業新聞社刊）のＣ言語...
-[[アルゴリズム系書籍ソース目次ファイル(Vector)>http://ww...
Vectorで公開されている~
『アルゴリズム演習300題』『C言語による最新アルゴリズム事...
-[[ソースコード探険隊 » アルゴリズムとデータ構造>ht...
データ構造の章では主に線形のデータ構造とグラフデータ構造...
アルゴリズムの章では主に探索アルゴリズムと整列アルゴリズ...
-[[Algorithm Collection>http://web.archive.org/web/200402...
(web.archive)~
-[[Windowsプログラミング研究所 » ゲーム＆その他>htt...
実践(アルゴリズム中心)~
-[[京都大学OpenCourseWare » 工学部 » アルゴリ...
-[[九州大学大学院システム情報科学研究院 金子研究室 Web ペ...
//www.db.is.kyushu-u.ac.jp -> www.kkaneko.com 移転。
-[[Fussyのホームページ > アルゴリズムの紹介>http://fus...
-[[アルゴリズム - osdev-j (MMA)>http://wiki.osdev.info/in...
-[[アルゴリズム辞典 [無料]>http://dir.kotoba.jp/ddcat.cgi...
-[[ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリ...
-[[技術計算用Ｃプログラム ソース>http://www5.airnet.ne.jp...
アルゴリズムをCソースプログラムと共に紹介、ダウンロード・...
終了行:
* アルゴリズムとデータ構造 [#p8c4a8bb]
この頁の解説貧弱すぎｗｗなめてんだろｗｗｗ~
と思った奴は何か書いてくれ
#contents
* 計算量 [#p6073ad2]
アルゴリズムがどれだけ効率的かを示す概念が''計算量''です...
具体的に、下に述べている[[線形探索>#oc5e463b]]の例で計算...
一般に、計算量がデータ数によらない定数（O(1)と書きます）...
なお、このような記法はあくまでnが大きい時に重要になるので...
* アルゴリズム [#v958b98c]
問題を解くための手順を''アルゴリズム''と呼ぶ。~
但し、アルゴリズムと呼ばれるためには以下の条件を満たさな...
・問題を解く上で正しいこと。
・手順が具体的に示されていること。
つまり、コンピュータで実行可能なように、曖昧さがなく記...
・有限の実行時間で、必ず終了すること。
** 探索 [#i297b629]
*** 線形探索 [#oc5e463b]
英語ではリニアサーチ。~
何のひねりもなく、先頭から末尾まで探していくだけのサーチ...
データが多くなると遅くなりがちですが、何の前提条件も無く...
シンプルなので、要素の数が10個前後の小規模な配列に対して...
例:C言語(配列のアドレスとサイズを渡し、numと一致する要素...
int linear_search(int *array, unsigned int size, int num...
int i;
for(i = 0; i < size; i++){
if(array[i] == num) return i;
}
return -1;
}
配列の要素数が増えれば増えただけ探索に時間がかかるように...
要素数10000の配列は、要素数10の配列の1000倍時間がかかるわ...
このように、データ量と処理時間が単純に比例して増える事を...
１番時間がかかるのは探しているデータが存在しない場合で、...
*** 二分探索 [#qce356fb]
英語ではバイナリサーチ。~
整列済みの要素群に対して実行します。 性質上、再帰を用い...
例:C言語(配列のアドレスとサイズを渡し、numと一致する要素...
int binarysearch(int * array , unsigned int size , int n...
int begin = 0; int end = size - 1; int center;
while(1) { //無限ループ
center = (begin + end) / 2;
if(array[center] >= num) { //num...
if(array[center] == num) { return center; ...
end = center - 1;
}
else { //num...
begin = center + 1;
}
if(begin > end) return -1; //探す範...
}
}
整列の中央と探索対象を比較すると、その結果で整列の
左側あるいは右側だけに候補を絞ることができます。~
そして、その搾られた候補に対して同じ要領で中央の値との比...
いずれある時の中央の値あるいはただひとつに絞られた候補と...
探索対象が現れます(整列に探索対象があれば)
要素数１の時の処理時間を基準にすると、要素数４でも３倍、...
１回の比較で、探索候補の半分を振るい落とせるためです。~
このように、データ量が倍に増えても処理時間は緩やかにしか...
線形探索のO(n)と比べるとデータ量の増加に強いものの、処理...
要素が少ないうちは線形探索よりも遅かったりしますが、総合...
** 整列 [#h84db045]
*** ボゴソート [#h92fd60b]
世間にはあまり知られておらず、専門書にもまず載っていない...
他のソートアルゴリズムに比べ極めて分かり易いアルゴリズム...
訓練をすれば猿はおろか犬でも習得できる。~
要素をランダムに並べ替え、順番に並んでるかを確認し、もう...
この操作をソートが完了するまで行う。~
運がよかったら一発で終了するがそうでない場面の方が圧倒的...
ソートが終了するかかどうかは「無限の猿定理」でぐぐると幸...
~
所謂ツンデレソート。「一回で終わるわよこんなソート！」~
一回で終わったためしがなく、バブルソートよりはるかに遅い。~
計算時間はO(n*n!)~
void swap(int* p1, int* p2)
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
void bogo_sort(int* array, int size)
{
srand((unsigned)time(NULL));
int i;
while(1){
int sort_flag = 0;
for(i = 0; i < size-1; i++){
if(array[i] > array[i+1]){
sort_flag = 1;
}
}
if(sort_flag){
int t1 = rand()%size;
int t2 = rand()%size;
swap(&array[t1], &array[t2]);
}
else{
return;
}
}
}
~
***バブルソート [#c164d24f]
初心者の坊や達を優しくソートの世界に導いてくれる方。~
とても素直だけど、遅いので実戦の場に出ず教育者として活躍...
例:C言語
void bubble_sort(int *array, unsigned int size){
int i, j, t;
for(i = 0; i < size; i++){
for(j = size - 1; j > i; j--){
if (array[j] < array[j - 1]){
t = array[j];
array[j] = array[j - 1];
array[j - 1] = t;
}
}
}
}
隣り合ってる要素を比べて、並べたい順番になってなかったら...
要素が正しい位置に泡のように登っていくのでバブルソートと...
単純ですが無駄な比較が多く、遅いです。
サンプルコードを見れば分かるように、ループを二重に回して...
***シェーカーソート [#eaad47d0]
バブルソートの親戚。~
挟みこむような動きで少しだけ無駄を減らす事に成功しました。~
カクテルソート等とも呼ばれます。 オシャレですね。~
バブルソートで走査中、最後に入れ替えがあった位置よりも後...
つまり、最後に入れ替えがあった位置を記録し、次からはそれ...
そこで更に、前方後方と交互に走査すれば、両方から範囲を狭...
%%ぶっちゃけ大して変わらないとか言うな。%%
実際計算量もO(n^2)。
***コムソート [#d6da5661]
バブルソートの親戚。~
色々な大きさの櫛を駆使します。~
隣同士ではなく、まず適当に大きな間隔を開けて比較・交換を...
どんどん間隔を小さくしていきつつ走査を繰り返し、最後は間...
この隣同士の交換が終わった時、既にちゃんと整列出来てしま...
ずっと細かく見ていくよりも、最初は大雑把にやった方が効率...
飛び飛びに揃えていくのが髪をとかす櫛（コム）のように見え...
計算量は理論的にはO(n^2)のはずですが、実験的にO(n log n)...
***挿入ソート [#b78ed62f]
手当たり次第に突っ込む単純な子ですが、状況次第ではなかな...
大変に開放的な性格です。~
例:C言語~
void insertion_sort(int *array, unsigned int size){
for (i = 1; i <size ; i++) {
for (j = i; j > 0 && array[j-1] > array[j] ; j--)
{swap(data[j-1] , data[j]); } //要素の交換
}
前から順に見ていき、要素を正しい位置に挿入していきます。~
この「挿入」の操作そのものは、バブルソートと同じような要...
動きとしては、配列の前部に 整列したデータがどんどん溜まっ...
ほとんど整列済みのデータなら離れた所まで挿入する事が少な...
計算量はO(n^2)ですが、そのような性質から、O(n log n)のソ...
*** シェルソート [#ua3da88b]
挿入ソートの親戚。~
やはり突っ込むばかりだけれど、少しずつ間隔を開けたりする...
別に貝殻が好きというわけではなく、Shellさんが開発しただけ...
挿入ソートとシェルソートの関係は、バブルソートとコムソー...
「最初は大雑把にやって、最後だけ細かく仕上げた方が効率が...
具体的には、ある程度の間隔を開けて挿入ソートを行い、どん...
*** 選択ソート [#t69c50e9]
馬鹿ソートとか言われたりするけど気にしない明るい子。~
とりあえず一番小さいのを探し続ければそのうち揃うよね！
配列を走査し、最も小さい(ソート後に端に来る)データを見つ...
そして、２番目の小さいデータ、３番目に小さいデータ、と次...
最後の１個を見るまで「一番小さい」かどうかはわからないた...
交換回数は少ないため、バブルソートよりは高速と言えます。
でも計算量はO(n^2)。
*** クイックソート [#h788cb12]
最速の名をほしいままにしているが、たまにさぼっちゃう気ま...
スレンダーな子です~
複雑と思われがちですが、実は意外と単純です。~
まず配列からある要素A（''ピボット''といいます）を取り出し...
次にAより前に振り分けられた部分からまた、ある要素Bを取り...
このようにある要素をピボットとして取り出し、それを基準と...
計算量は分割の回数が大体O(log n)、各ステップ毎にO(n)かか...
このように効率の悪いピボットを選ぶ可能性を排除するため、...
クイックソートの重要な欠点としては、他に不安定であること...
void sort(int*a,int s){
int i=-1,j=s,p=a[s/2],t;
for(;;){
while(a[++i]<p);
while(a[--j]>p);
if(i>=j)break;
t=a[i];
a[i]=a[j];
a[j]=t;
}
if(0<i-1)sort(a,i);
if(j+1<s)sort(a+j+1,s-j-1);
}
*** マージソート [#y34cbfeb]
いつも手を抜くことなく、速さを常に追求する努力家~
クイックソートには負け越しているのをくやしがっている~
他の子より大きいのが悩み~
まず、配列を真っ二つに分けます。 分かれて出来た２つの配...
これを繰り返し、完全にバラバラになってしまうまで分割して...
分割が終わったら、今度は逆にマージ(合併)していきます。 ...
マージして出来た配列を更にマージしていって、最後にたった...
綺麗に並んだ配列２つをマージする時は、それぞれの配列の「...
（１，４，５）と（２，３，６）なら、まず左端の１と２だけ...
マージにO(n)の余分なメモリ領域が必要な事と、平均するとク...
それだけじゃクイックソート使えばいいじゃないかとなります...
外部記憶が必要なくらい大きなソートをする場合クイックソー...
また、安定ソートでもあります。 なんとなく堅牢なイメージ...
*** ヒープソート [#l50b875a]
[[ヒープ>#v35e1d11]]構造を利用したソート。計算量はO(n log...
*** バケットソート [#b490822c]
他にもビンソートとか色々あだ名がある。~
趣味で大量にバケツを集めすぎて家を崩壊させてしまうような...
秘めたポテンシャルを発揮出来ずにいる。
「０～１００点のテストの点数をソートするんなら、１０１個...
という事をマジでやるというトンでもなく豪快なソートです。~
比較と入れ替えを繰り返すものが多いソートの中で、非常に独...
まず、データがいくら増えようと「バケツに入れる」という操...
（データ量が千倍になればクイックソートでも大体１万倍重く...
非常に速いソートですが、当然弱点があり「バケツを用意する...
例に出した0～100の範囲ならまだいいのですが、32bitのint型...
範囲は-2,147,483,648～2,147,483,647という事で、4294967296...
また、ソートしたいデータに同じ数値が重複してる場合があり...
バケツは単純な配列として用意する事は出来ません。配列には...
大抵はリンクリストの配列みたいな実装になるのですが、リン...
このように、使うための条件は厳しいものの、計算量は通常の...
*** 分布数えソート [#r779f37a]
バケットソートの親戚。~
一応バケットソートよりはマシなものの、やはり家が崩壊しが...
バケットソートはリンクリストを使った実装だと 動的なメモリ...
なので、もっと上手い方法は無いのか、という事で考え出され...
まず、以下のようなデータがあったとします。
0 1 2 0 0 3 1 2 0 2 2 0
これを昇順にソートすると
0 0 0 0 0 1 1 2 2 2 2 3
このようになるわけですが、最も左を「0番目」として数えると~
0は0番目から、1は「0の個数(5)」である5番目から、2は「0の...
3は「0の個数(5)＋1の個数(2)+2の個数(4)」である11番目から...
これを利用し「何番目から始まるか」という数だけをバケツに...
同じ数値が重複してても、その要素を処理するたびに「何番目...
このような実装をすれば リンクリストのための余分なメモリも...
ただし、要素の数を数えるための走査と 実際にソートをするた...
ソートしようとしているデータの規模によってはかえって低速...
(リンクリスト用のメモリの動的確保や分岐は結構重いので、測...
*** 基数ソート [#od200194]
バケットソートの友人。 英語にするとラディックスソート。~
極限られた状況でのみ他を圧倒する速さを出す可能性を秘めて...
しかし、あまり活躍の機会がないのでたまに忘れ去られてたり...
基数というのは数を表す際に基本となるまとまりの事で、例え...
１桁目、２桁目、３桁目のように桁ごとにソートしても、順番...
以下のようなデータがあったとします。
19 70 35 48 24 14 40
これを１桁目だけに注目して、小さい方を左に来るようにソー...
70 40 14 24 35 48 19
更に、この順番をなるべく保ったまま２桁目だけに注目してソ...
14 19 24 35 40 48 70
このように、結果的に綺麗に揃っており、これは3桁に増えよう...
例えば、バケットソートで0～9999の範囲を整列せねばならなく...
これを利用して「下２桁を基準にソート→上２桁を基準にソート...
当然、分けただけソートの回数は増えますし、分ける事そのも...
バケットソートほどの速度は出ないのですが、それでも十分速...
速度を求めるなら割り算や剰余ではなく、CPU的にキリの良い２...
「桁ごとに区切っても揃う」という原理は別にバケットソート...
その他のソートだと単に処理の回数を増やすだけで何の利点も...
「バケットソートは超速いけど、メモリ喰いすぎるのがちょっ...
範囲さえある程度絞れるならクイックソートよりも普通に高速...
工夫次第で負の数を含んでたり浮動小数を扱ったりする場合に...
*** 逆写像ソート [#pfbe4b79]
バケットソートの親戚。~
一見、数学的で難解な事を考えていそうな雰囲気ですが、割と...
写像とは小難しそうな数学用語ですが、「２つの数字の集まり...
添字を入れると要素が出てくる配列も 添字→要素の写像と言え...
「逆写像」というと、その逆になり、要素→添字という写像にな...
そういう配列＝バケツと考えると、実の所それはただのバケッ...
バケットソートとの違いは「値が同じ要素があった時の対処」...
その対処の仕方とは「添字をポインタ代わりに使ってリンクリ...
リンクリストでいう next に対応する添字の値を確保するため...
この配列のおかげで、バケツに１つの要素しか入れる必要が無...
ぶっちゃけバケットソートや分布数えソートを使えば済むので...
*** 奇遇転置ソート [#f9f10dce]
バブルソートの親戚。~
チームプレーや流れ作業が得意な方。
バブルソートは隣合った要素を比較、交換していくので~
「１ ２」「２ ３」「３ ４」を添字として処理していくわ...
奇遇転置ソートは「１ ２」「３ ４」「５ ６」のような「...
「２ ３」「４ ５」「６ ７」のような「偶数 奇数」要素...
処理の回数そのものはバブルソートと大して変わらないのですが~
ポイントは「１ ２」「２ ３」 だと「２」が かぶってます...
つまり１回１回の処理が独立しているため、複数のCPUを使って...
いくら大量にCPUがあっても、走っているスレッドが１つだけな...
CPUを増やせば増やしただけ速く出来るという限界の高さに並列...
逆に言えば、並列処理が出来る環境でなければ大して役に立た...
*** シェアソート [#ya8737c6]
共有のソート。~
部下を団結させ、隊列を整えるチームワークを発揮させるやり...
一次元の住人が多いソート業界では珍しい二次元の世界の住人...
まずは、要素数[30]の配列→[6][5]の二次元配列、みたいな感じ...
そして１行目[1][i] ２行目[2][i] ３行目[3][i]……のように...
１列目[i][1] ２列目[i][2]……のように各列別々にソートする...
各行や列は、それぞれ独立しているので、並列に処理が出来ま...
「奇数行は左が小さくなるように、偶数行は、右が小さくなる...
「列は、上が小さくなるようにソート」~
これを交互に繰り返す事で、小さい値は左右にクネクネ動きな...
ちなみに、各行に対して行うソートは何を使ってもいいですが~
奇遇転置ソートやマージソート等を使うと並列性を更に上げら...
複数のCPUを搭載している状態なら、かなりの速度向上が期待出...
もちろん、並列処理が出来る環境でなければ、さほどのスピー...
*** バイトニックソート [#ud51908c]
究極のスピードを誇っているものの、力を出しすぎると地球が...
が・・・あ・・・離れろ・・・死にたくなかったら早く俺から...
理論上最高の速度が出るソートですが、やってる事は凄く単純で~
if や else等の分岐を大量に使って最小限の回数の比較、交換...
性質上、ソートする配列のサイズがわかってて、しかも極端に...
要素の数が４つだけの場合でも使うifやelseの数は数十個に及...
書くのが異様に面倒なので、実際に使いたいなら そういうコー...
また、当然実行ファイルのサイズも爆発的に増えていきます。 ~
何億回もソートを繰り返すような処理が必要でなければコスト...
※どうやら上記のソートは本来の(？)バイ・トニックソートとは...
本格的なバイ・トニックソートは、むしろマージソートに近...
正確な情報はちょっと持ってないので、知ってる人は編集し...
*** 安定ソートと、そうでないソート [#h37e2e26]
等価なデータの順番がソート前と同じという事が保証されてい...
言葉にすると難しいですので例を出しましょう。
例えば、このようなデータがあるとします。~
データ 「A：50」「B：20」「C：80」「D：20」「E：60」
これを「数字だけを基準に、小さい方が左に来るようにソート...
結果１ 「B：20」「D：20」「A：50」「E：60」「C：80」
結果２ 「D：20」「B：20」「A：50」「E：60」「C：80」
このどちらかになる事が予想出来ますが~
安定ソートだと「元々Bの方が左にあった」という事で、必ず結...
クイックソート等の安定でないソートを用いると、結果１にな...
「そんなのどうでもいいから速いほうがいいよ」という場合に...
多くのソートが安定ですが~
コムソート シェルソートなどの間隔を開けて処理をするソー...
クイックソート等は、安定でないソートとして知られています。
安定と言われているソートでも、実装の仕方によっては安定で...
あえて安定にしない事で得するような事はあまり無いです。~
また、基数ソートのように安定なバケットソートを利用しない...
** 最短経路問題 [#lf212c0c]
*** ワーシャル・フロイト法 [#f8c41450]
こいつはなぁ、全通り調べるんだよ
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
for(k = 0; k < n; k++){
if(array[j][k] > array[j][i]+array[i][k]){
array[j][k] = array[j][i]+array[i][k];
}
}
}
}
jからkに行くまでのコストについて比較してる
j→kとj→i→kっていくのがどっちが安いのか
こうすると自然に最短経路が埋まる
3重ループは全通り調べられるから他のアルゴリズムにも使える
このアルゴリズムは要素が多いときは不向き
*** ダイクストラ法 [#l7e4f36c]
ダイクストラとは、かの有名な論文''"Go To Statement Consid...
難しそうに見えて実は簡単・・・じゃないか
じゃあこの問題があったとしよう
夏休みにニートのvipeerは旅行に行こうとしましたが働いてい...
親から金をもらいに行く勇気のなかったvipperは極力少ないお...
ここで出発地から目的地まで行く最低のコストを求めよ
また、要素の数nは10まで、nが入力されたあとa b cが入力さ...
最後の行にs,gは入力されsは出発地、gは目的地である。
またbからaにも同じだけの値段がかかるとし、a,bはnまでの数...
こんなもんワーシャルフロイドでやれや(笑)って言わないでね
入力のところは
#include<stdio.h>
#define MAX (10)
int main(void)
{
int n;
int a, b, c;
int i;
int cost[MAX][MAX]; // それぞれの場所までの値段
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d %d %d", &a, &b, &c);
cost[a][b] = c; // aからbに行くまでの値段
cost[b][a] = c; // bからaに行くまでの値段
}
return 0;
}
これが基本
ここからダイクストラを実装すると
for(i = 0; i < n; i++){
used[i] = 0; // すべて使っていないことにする
val[i] = INT_MAX; // すべてのコストを最大にする
}
val[s] = 0; // 出発地のコストは0
while(1){
minVal = INT_MAX;
for(i = 0; i < n; i++){
// 確認してないで 一番安い出発地からのコストが一番安...
if(used[i] == 0 && val[i] < minVal){
minVal = val[i];
min = i;
}
}
// もしすべて確認が終わったとき終了する
if(minVal == INT_MAX){
break;
}
used[min] = 1; // 使用済みにする
for(i = 0; i < n; i++){
// minからiにいけてかつ最小コストの時更新
if(cost[min][i] && cost[min][i] + val[min] < val[i]){
// minからiまで行く値段と出発地からminにくるまでの...
val[i] = cost[min][i] + val[min];
}
}
}
こうなる
時間がないからまた今度書く
全体は
#include<stdio.h>
#include<limits.h>
#define MAX (10)
int main(void)
{
int n;
int a, b, c;
int s, g;
int i, j;
int cost[MAX][MAX]; // それぞれの場所までの値段
int used[MAX]; // 確認済かどうかのフラグ
int val[MAX]; // 出発地からのコスト
int minVal, min;
scanf("%d", &n);
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
cost[i][j] = 0; // 初期化しておく
}
}
for(i = 0; i < n; i++){
scanf("%d %d %d", &a, &b, &c);
cost[a][b] = c; // aからbに行くまでの値段
cost[b][a] = c; // bからaに行くまでの値段
}
scanf("%d %d", &s, &g);
for(i = 0; i < n; i++){
used[i] = 0; // すべて使っていないことにする
val[i] = INT_MAX; // すべてのコストを最大にする
}
val[s] = 0; // 出発地のコストは0
while(1){
minVal = INT_MAX;
for(i = 0; i < n; i++){
// 確認してないで 一番安い出発地からのコストが一番...
if(used[i] == 0 && val[i] < minVal){
minVal = val[i];
min = i;
}
}
// もしすべて確認が終わったとき終了する
if(minVal == INT_MAX){
break;
}
used[min] = 1; // 使用済みにする
for(i = 0; i < n; i++){
// minからiにいけてかつ最小コストの時更新
if(cost[min][i] && cost[min][i] + val[min] < val[i...
// minからiまで行く値段と出発地からminにくるまで...
val[i] = cost[min][i] + val[min];
}
}
}
printf("%d\n", val[g]);
return 0;
}
*** A* [#g531e457]
A*と書いて「エースター」と読む。~
ダイクストラ法は「出発地から経由地までのコスト」が最小と...
A*はこれに加えて「経由地から目的地までのコスト」も参照す...
そして、それぞれのコストの和が最小となるように次の経由地...
ただし、このアルゴリズムの適用にあたって注意がある。~
それぞれの経由地から目的地までのコストが分かっていないと...
と言っても、正確なコストはこれから調べるんだから分かるわ...
そこで、「たぶんこれくらいのコストだろう」という値を用い...
この時のコストの見積もりは、実際のコストより「必ず」低く...
証明は省略するが、最短経路を求める条件として必要だからだ。~
そのような見積りとしては、例えば目的地までの直線距離なん...
** 動的計画法 [#se794f0d]
* データ構造 [#wc0c038f]
** 配列 [#p0a42e9d]
気にしたことないだろうけど、配列も立派なデータ構造なんだ...
重要なことは、多くの言語やその処理系でO(1)のアクセススピ...
つまり、ほかのデータ構造に比べて単純な分、早いんだなこれ...
馬鹿とはさみは使いようってやつだな。
** スタック [#e04037cc]
お菓子でいうとPEZ(ペッツ)
「干し草の山」の意。~
名前の通り、新しいデータを上に積み上げていき、下に埋もれ...
上のデータを先に取り出さなければならない後入先出(あといれ...
「古いデータは取っておき、新しいデータに対して色々な処理...
例えば関数・メソッドの呼び出しの際に使われるコールスタッ...
ローカル変数は他の関数を呼び出してから戻ってくるまでずっ...
** キュー [#x9b212e8]
ところてんだよところてん
「待ち行列」の意。
名前の通り、古いデータは新しいデータの後ろに並び、新しい...
先入先出(さきいれさきだし)の構造です。~
「先のデータの処理が終わるまで、後から来たデータにちょっ...
サーバーなんかは、すぐに処理出来ない大量のリクエストが来...
(優先度が高いリクエストはキューで待たせず割り込ませてあげ...
mallocとか使わないクズキュー~
#define QMAX 100
typedef struct{
int que[QMAX];
int hp,tp;
}queue;
void init(queue* q)
{
q->hp = 0;
q->tp = 0;
}
int isempty(queue q)
{
return q.hp==q.tp;
}
void push(queue* q,int n)
{
q->que[q->tp++]=n;
if(q->tp==QMAX)q->tp=0;
}
int pop(queue* q)
{
int res=q->que[q->hp++];
if(q->hp==QMAX)q->hp=0;
return res;
}
こんな感じで使う~
http://ideone.com/Dt13X
** デック [#gffe4778]
Deque。 スタックとキューを合わせたような機能を持っていま...
具体的には「前から入れる」「前から出す」「後から入れる」...
長所：両端へのデータ挿入がO(1) 添字アクセス可能~
短所：要素の中央の挿入、削除が遅い
削除、挿入は平均すると動的配列より優れるが、単純なアクセ...
** リスト [#n30cdd26]
連結リストとも呼ばれる非常に一般的なデータ構造の一種。~
ある箱を仮想的に考え、それと別のはことをつなぐようなイメ...
箱は変数を表すと考えれば、箱同士のつなぎ方によっていくつ...
多くの言語では、箱と連結部分を一括して扱うために、構造体...
最近のモダンな言語ではライブラリにリスト構造があらかじめ...
また、Lispなど「リスト構造ありき」で言語設計がなされてい...
似たようなデータ構造に配列が存在するが、N番目の要素にアク...
従って、使用できるメモリーの割合や扱うデータの特性によっ...
リストが有利なのは、極めてデータ数が大きい際に、頻繁に途...
*** 単方向リスト [#c3b02503]
リストの要素同士を連結するとき、A→B→C→……のように、一方向...
このとき、例えばある要素を検索したい場合、現在の位置をAと...
通常、リストといえばこちらを指す。~
一方向への連結しかみないので管理が楽で、使用する領域も少...
電話帳のように、前の要素に戻る必要が生じにくいデータの表...
*** 双方向リスト [#sf7d12f5]
単方向リストと異なり、逆順にも辿れるようにしたリスト。~
単方向リスト同様、矢印表記を用いれば、A⇋B⇋C⇋D⇋……と表すこ...
特徴は、ある要素Nへのアクセスオーダが必ずしもO(N)にならな...
現在位置を覚えておきつつ、前後の要素にアクセスするような...
*** 循環リスト [#wbdee299]
上記二つのリストのどちらとも併用できる連結方法で、リスト...
通常、リストの末尾の次の要素は、NULL等の末端であることを...
例えば、あるデータを検索するときに、末尾まで検索したら先...
** 木 [#j0b14123]
上記で色々解説されてる配列・スタック・キュー・リストなど...
一方で、木構造というのは枝分かれのあるデータ構造だ。一つ...
ただし、大抵の場合、図示するときは木みたいに下から上に生...
木構造で有名なのは、ファイルシステムだ。WindowsならCドラ...
後はXMLとかJSONとかも一種の木構造だし、ドメイン名の集合な...
ここからしばらく木構造に関して解説を加えよう。木構造の解...
- ノード（節） 木構造を構成する基本単位。0個又は1個の親...
- ルート（根） 木構造の一番根本にあるノード。任意の子ノ...
- リーフ（葉） ルートとは逆に、木構造の一番末端にあるノ...
- エッジ（辺） 親ノードと子ノードを結ぶ線。~
- 先祖ノード 任意の子ノードから辿って、ルートに辿り着く...
- 子孫ノード 任意の親ノードから、子ノードを辿って到達す...
- 深さ 任意のノードのルートまでのエッジの本数。ルートの...
- 高さ 任意のノードから一番深い子孫リーフまでのエッジの...
*** 二分木 [#d6d2cafb]
木構造のうち、子ノードの数が2個以下のものを2分木という。...
二分探索と相性が良く、実装が簡単なため良く利用される。~
以下で紹介するAVL木、赤黒木、ヒープは全て二分木の実装だ。~
*** AVL木 [#l4384105]
単純な二分木の構成だと、値を挿入する順番によっては単なる...
そうなると、探索・挿入・削除の計算量がO(n)になってしまう...
平衡二分探索木は、ノードの左右の深さがほぼ等しい二分木を...
平衡二分探索木の探索のコストはO(log n)になる。~
AVLは平衡二分探索木のなかでも、厳密な平衡性を保つアルゴリ...
厳密な平衡性を保つためには、ツリーに偏りが生じた場合、回...
*** 赤黒木 [#x3cd9897]
赤黒木はあまり厳密に平衡性を保たない平衡二分探索木だ。具...
したがって、AVL木と比べると探索にかかるコストは大きい。~
一方で、赤黒木は挿入・削除時の回転の回数を減らすことがで...
赤黒木は動的なデータ構造、AVLは静的なデータ構造といった風...
*** ヒープ [#v35e1d11]
** グラフ [#f9136e1b]
*** 隣接行列表現 [#qbdd8249]
*** 隣接リスト表現 [#k4751445]
** ハッシュ表 [#f7c93b36]
*** 連鎖法 [#l66cfcc0]
*** オープンアドレス法 [#e44025a1]
*その他 [#bbfb5391]
**最大公約数(GCD: greatest common divisor) [#i9b377e0]
(ユークリッドの互除法)~
紀元前300年頃には既に存在した、最古のアルゴリズム。~
例 a0 = 497,a1 = 284とおく。
497 = 284 + a2 a2 = 213
284 = 213 + a3 a3 = 71
213 = 71 * 3 + a4 a4 = 0
つまり、497と284の最大公約数は71となる。
この計算手法をユークリッドの互除法と呼ぶ。
実装例:C言語
#include <stdio.h>
int gcd(int a0, int a1)
{
int a, b, tmp;
a = a0; b = a1;
while (b != 0) {
tmp = a % b; a = b; b = tmp;
}
return a;
}
上記GCD関数用のテストコード
int main(void)
{
int a0, a1, tmp;
printf("一番目の整数を入力してね >> ");
scanf("%d", &a0);
printf("二番目の整数を入力してね >> ");
scanf("%d", &a1);
if (a0 <= 0 || a1 <= 0) {
printf("0以下の数なんか入力すんなｗｗｗ : %d, %d...
exit(-1); // 異常終了
}
if (a0 < a1) { // 関数GCDではa0 > a1と仮定しているの...
tmp = a0; a0 = a1; a1 = tmp;
}
printf("%d と %d の最大公約数(GCD) = %d\n", a0, a1, ...
return 0;
}
** 参考リンク [#d212128a]
-[[C言語による最新アルゴリズム事典(Vevtor)>http://www.vec...
『C言語による最新アルゴリズム事典』全ソースコード~
-[[アルゴリズム演習300題(Vector)>http://www.vector.co.jp/...
「アルゴリズム演習３００題」（日刊工業新聞社刊）のＣ言語...
-[[アルゴリズム系書籍ソース目次ファイル(Vector)>http://ww...
Vectorで公開されている~
『アルゴリズム演習300題』『C言語による最新アルゴリズム事...
-[[ソースコード探険隊 » アルゴリズムとデータ構造>ht...
データ構造の章では主に線形のデータ構造とグラフデータ構造...
アルゴリズムの章では主に探索アルゴリズムと整列アルゴリズ...
-[[Algorithm Collection>http://web.archive.org/web/200402...
(web.archive)~
-[[Windowsプログラミング研究所 » ゲーム＆その他>htt...
実践(アルゴリズム中心)~
-[[京都大学OpenCourseWare » 工学部 » アルゴリ...
-[[九州大学大学院システム情報科学研究院 金子研究室 Web ペ...
//www.db.is.kyushu-u.ac.jp -> www.kkaneko.com 移転。
-[[Fussyのホームページ > アルゴリズムの紹介>http://fus...
-[[アルゴリズム - osdev-j (MMA)>http://wiki.osdev.info/in...
-[[アルゴリズム辞典 [無料]>http://dir.kotoba.jp/ddcat.cgi...
-[[ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリ...
-[[技術計算用Ｃプログラム ソース>http://www5.airnet.ne.jp...
アルゴリズムをCソースプログラムと共に紹介、ダウンロード・...
ページ名:
