タイトル考えつかない

　先日，AOJの問題をいくつか解いていて，「ソートも出来ない自分はコンテストで爆死するのかなぁ」とか考えてしまった．そこで，今日からまともなアルゴリズムの勉強を始めたいと考え付いた．

そもそもアルゴリズムってなんだっけ

　簡単(にしたとは書いていない)に纏めると，

• 処理を示す手順

の事を意味している．基本的にアルゴリズムは考え方又は手順なので，言語間での差異が発生するのは少ない．プログラム言語の参考書をいくら読んでも，アルゴリズムの知識が無ければ，ただ時間を削っただけにしか過ぎない(全て無駄ではないが，少なくとも自分はそうだった)．アルゴリズムとその言語に関する知識があって，初めてまともにプログラミングという行為が成り立つのでは，と思い始めてきた．

計算量

　一まとめにアルゴリズムといっても，それぞれ多種多様な特徴がある．実行速度が速いものから遅いもの，実装する量が多いものや少ないもの(残念ながら，自分は最短経路問題やDPでしか見た事が無い)など，様々なものがある．例として，バブルソートのコードは単純で書き易くても，実行速度は遅い．また，コンピュータの性能によっても実行速度には差が出る．そのため，これらの実行速度を客観的に評価するものが，計算量である．基本，これはO記法が用いられる事が多い．

O記法

　O記法の書き方として，n個のデータ列をn時間で処理する時，O(n)として表す．例えば，先ほどのバブルソートもO記法で表せばO(n^2)となる．頻出例は以下の様になる．

表記	意味	例
O(1)	定数	添え字による配列アクセス
O(log n)	対数	二分探索
O(n)	1次	線形探索
O(n log n)	n log n	クイックソート
O(n^2)	2次	2重ループ，配列全体走査
O(n^3)	3次	3重ループ，配列全体走査
O(2^n)	指数	集合分割問題

線形探索法のコードで考えると次の様に書ける．これは，n個のデータが登録されているデータから，目的の値を持つデータを探索するもので，登録されているデータの数が大きければ大きいほど計算回数が増えていく．

#include<stdio.h>

struct{

    int key;

    int data;

} table[100];

int n;

int serch(int key){

    int i;

    i=0;

    while(i<n){

        if(table[i].key==key)   return (table[i].data);

        i++;

    }

    return -1;

}

　このとき，関数serchが呼び出され，i=0;が実行される．次に，while文と中のif文が真になるまで実行される．このとき，最小計算量は，whileループ内で1回目で目的の値が見つかった時=O(1)，最大計算量はn回分のループを繰り返しても目的の値が見つからなく，-1を返したとき=O(n)，となる．よって，これらの計算量はmin=O(1),max=O(n)となる．

　いったん，ここで切る事にする．唐突に思い立って何も考えずに書いたら以上のようにぐだぐだと書き連ねる事になってしまったので，次はある程度プロットを起こしてから書き出すようにしたい．