けんつの煽られ駆動開発記

何か作るときは大抵誰かに煽られた時です。

ちょっとしたアルゴリズムのお話

今回は普段の画像処理、ネットワークプログラミングの話から少し変わって

 

アルゴリズムのお話

 

ということでさくっとまとめていく

 

まず、プログラムとは

 

問題解決の為に

 ・何をプログラムするか

 ・解決策を選択する

 ・コードにする

ことからなる

 

つまりアルゴリズムを考えることであり解決策を考えることでもある

 

しかし、実際には問題分析において高校までの数学の様にこうすればOKとか

そういった定石が存在しない

 

なので、適切なアルゴリズムとデータ構造を選択する

また選択肢を増やすための知識の蓄積が最も重要となる

 

また、アルゴリズムだけ学べばいいのではなく

データ構造についても学習する必要がある

 

それはアルゴリズムは単なる方法、手段に過ぎないから

実際にはデータ対してアルゴリズムを用いるためデータがどういった構造をしているか

 

また、アルゴリズムを適応しやすいデータ構造である必要があるから

 

 

またここまで理解した上で重要となるのは

 

時間と空間のトレードオフと計算量という概念である

 

アルゴリズムを組む上で

 

・時間はかかるがメモリをあまり使わないもの

・時間はかからないがメモリを多く使うもの

 

空間(ここではメモリ)を犠牲にするか、時間を犠牲にするか

一方を犠牲にすれば、他方が伸びる

こういった関係にあるものを

時間と空間のトレードオフという

 

次に計算量

 

多少なりとも勉強したことがある人なら聞いたことはあるであろう計算量

O(n)と表記されることもあり、nのオーダー、オーダーnという

 

計算量とはそのままの意味で、アルゴリズムの性能を示す一つの指標となる

 

 

アルゴリズムでどれだけ処理に時間がかかるかというものを、時間計算量

必要なメモリの量などから判断するものを、領域計算量という

 

この2つは時間と空間のトレードオフを考慮する上で非常に大事な関係にある

 

また計算量を求めるとき

平均の計算量をそのまま平均計算量といい

最悪の入力があった場合のものを最大計算量といい

 

普通は計算量というとき最大計算量を意味する

 

ここまでがアルゴリズムの定義でつまらない決まりの話

 

実際にアルゴリズムを組んでみると、ここまで話した計算量

特に、平均計算量と最大計算量についてわかると思う

 

 

例題:線形探索と二分探索

 

ここで、線形探索とはなにか

ざっくり言えばfor文とif文でかたっぱしから要素を探すアルゴリズムのこと

よくなぜそう言いたいのかわからないけど、先頭から探索なのに線形探索と言いたがる人がいるが、ただfor文で最初から回してるだけ

 

線形探索アルゴリズムの機能のみを実装。それ以外のエラーやバグなどは発生する可能性あり

 

本当に単純なアルゴリズムで、もはやアルゴリズムと呼べるか怪しいレベルに単純で性能の低いものである

 

この時最大計算量はO(n)となり、平均計算量はO(n/2)となる

つまり線形探索は要素数nが大きければ大きいほど、探索にかかる時間が露骨に増えてしまうアルゴリズムである

 

次に二分探索

これは、配列やリストがソートされている場合、要素数がある程度大きくないと使用できないアルゴリズムである

 

それは二分探索自体の仕組みにある

二分探索は、文字通り配列やリストを半分にして探索したい要素がどの範囲にあるかを判断し絞っていくので

素数が大きくないと範囲を絞り切れなかったり、要素が探索外の範囲にいってしまう場合がある

 

二分探索を実装してみた。あってるかわからん

 

この場合、二分探索では要素数nに対して最大計算量がO(log n)となり

線形探索よりも速いアルゴリズムとなる

 

この時、考えて欲しいのはオーダーのカッコ内に現れる要素数nとした場合のnを含む式である

 

線形探索はnについて一次式、つまり直線を表すものであるのに対して

二分探索はnについて自然対数の式、つまり曲線になった

 

これは要素数が肥大しても二分探索はそれほど計算量が増加しないことを示す

 

このように計算量やデータ構造を考え適切なアルゴリズム選択をすることで

プログラム自体の効率化につながる