オーダー再考〜O(n)は効率が良いのか〜

0. オーダーって何?

1. ソート

ソート（ソーティング，並べ替え，整列）のアルゴリズムについて， $O(n^2)$ になるもの， $O(n \log n)$ になるもの， $O(n)$ になるものが知られています．
$O(n^2)$ というのは，2重ループを使ったソートです．素朴なソートアルゴリズム，と言ってもいいでしょう．バブルソートや選択法なんかが当てはまります．
$O(n \log n)$ になるソートで有名なのは，クイックソートです．再帰（分割統治法）を使うアルゴリズムという点でも，学ぶ価値があります．なのですが，クイックソートは，ソートされる配列の並びが極端だと， $O(n^2)$ になることも知られています．そこで，クイックソートの平均時間計算量は $O(n \log n)$ ，最悪時間計算量は $O(n^2)$ ，なんて言い方をします．
2つの値の比較を繰り返すようなソートでは，オーダーは $O(n \log n)$ よりも小さくすることはできません．logが出てくる理由を簡単にいうと，n個の点からなる平衡2分木の高さが， $O(\log n)$ となるからです．
しかし，2つの値の比較をしない方法をとれば， $O(n)$ となるものもあります．基数ソートやバケツソートが知られています．値に何らかの性質を仮定することで， $O(n \log n)$ の限界を破っています．

2. 文字列パターンマッチング

ある文字列Sの中に，探したい文字列wがどこにあるかを求めるアルゴリズムも，良いもの・悪いもの，いろいろあります．パターンマッチングのほか，照合，文字列検索とも言います．このときは，検索対象の文字列の長さ|S|＝mと，探したい文字列の長さ|w|＝nという2つの変数を使って，オーダーを表記します．
素朴な方法は，Sの先頭がwと一致するか，Sの2番目の文字から始まるのがwと一致するか…と試すものです．この場合，オーダーは $O(mn)$ となります．これは，Sのそれぞれの文字が，wの各文字と1回ずつ，だから全体としてはn回，比較しているからです．
それに対して，Sのそれぞれの文字は，パターンマッチングを通じて1回しか読み出されない，比較されないように，することができます．wの内容に基づいて，テーブルを作っておくのが常套手段です．その場合，テーブル生成で $O(n)$ ，正味の検索で $O(m)$ となるので，全体としてのオーダーは $O(m+n)$ です．クヌース-モリス-プラット法，頭文字をとってKMP法というのが考案されています．

3. 数論アルゴリズム

情報セキュリティでは，べき剰余だとか拡張ユークリッドの互除法だとか，素因数分解だとか離散対数だとかで，数論（整数論，初等整数論）と関わるアルゴリズムが出てきます．
そこでは通常，入力となる値nに比例するようなアルゴリズムは，効率が悪いとされます．
離散対数問題を例にとると， $y=g^z \bmod p$ という等式があって，いずれも正の整数で，y, g, pが既知のとき---pが素数であるほか，もう少し条件がつくのですがここでは省略します---，zを求めます．
明らかにどんくさい方法ですが，zに，解の候補を代入すれば，解は見つかります．z＝1のとき，等号は成立しない，z＝2のとき，等号は成立しない，…とチェックするわけです．zが比較的小さい値のときに「当たり」が出るかもしれませんし，かなり大きな値にならないと，見つからないかもしれません．
解の候補の上限は，フェルマーの小定理から，p-2となります．そこで，答えが見つかるまでの，式評価の回数は， $O(p)$ と表せます．
比例だったらずいぶん速いように見えますが，「時間計算量は，入力の長さについての関数で表す」ことに注意しないといけません．入力は，yとgとpの2進表現，いわゆるビット列ですが，ここではpのビット列のみを考慮することにします．
pのビット長をbと書きましょう．すると， $2^{b-1}$ ＜ $p$ ≦ $2^b$ になります．
ランダウの記号をかぶせると， $O(2^{b-1})$ ≦ $O(p)$ ≦ $O(2^b)$ *1となるわけですが，この連立不等式の左と右は，オーダーとしては同じ $(2^b)$ になります．挟み撃ちの原理で， $O(p)=O(2^b)$ です．結局のところ，入力長の指数時間となって，効率が悪いアルゴリズムです．
セキュリティに関連するオーダーについては，kを定数として， $O(n^k)$ は多項式時間で効率が良く， $O(k^n)$ は指数時間で効率が悪い，と覚えておきましょう．また，ブルート・フォース・アタック（力ずく法，全探索）は，探索空間のサイズに比例するけれども，多くの場合それは，入力長（ビット長）の指数関数になるので，効率が悪いのです．

4. 検索

文字列に限定せず，要素数nの1次元配列の検索を行うアルゴリズムでは， $O(n)$ は，効率が悪いアルゴリズムです．
2分探索を用いれば， $O(\log n)$ になります．ただしそれを適用する場合，配列がソート済みであることが不可欠です．
ソートしてから検索すると， $O(n \log n)+O(\log n)$ ＝ $O(n \log n)$ となって $O(n)$ よりも効率が悪いことになります．さてどうしましょう?
検索については，次のような考え方があります．配列の内容は，実行時に入力として与えるのではなく，あらかじめ分かっているものとします．そして，検索を本当にするまでに，時間があるものとします．
そういった前提があれば，配列を， $O(\log n)$ で検索できるようにセッティングしておきましょう．「前処理」です．オリンピックの100m走者は，4年間をかけて，金メダルを得た瞬間をイメージし，体調を整え，服装や靴にも気を配っています．大学の需要の検索プログラムで，世界一は求めなくてとしても，事前の準備に手間をかけておき，検索そのものは一瞬でやってしまおうというのが，情報検索の基本的な考え方です．
その場合，配列を並べ替えるというよりは，正味のデータを持つところと，検索に使用するところとを分けて管理するのが一般的です．「検索に使用するところ」は，インデックス（索引）といい，それを作成することをインデクシング（インデキシング，索引付け）と言います．

5. まとめ

ここまで，アルゴリズムごとに，良いオーダーと悪いオーダーを見てきましたが，視点を変えて，「 $O(n)$ は効率が良いのか?」を考えることもできます．
$O(n)$ は，問題を解く対象によって，それが最も効率の良いアルゴリズムとなったり，素朴な時間の見積もりであって，もっと改善できるアルゴリズムの存在が示唆できたり，「入力長」に着目すると，実は線形どころか指数関数になったりします．
今回は，学科の2〜3年生が，いくつかの授業で学ぶと思われるアルゴリズムを見ていきましたが，「素朴な方法」「洗練された方法」の区別や，研究室で研究に携わり，アルゴリズムの改善をする必要があるといったときに，見直してくれればと思います．

6. 何これ

昨日の情報セキュリティの授業で話したことを，肉付けしました．
文字列パターンマッチングと，受講者の多くが1年後期に学んでもらった，フィボナッチ数計算のアルゴリズム *2については，用意はしていたものの授業中に話せませんでした．

*1:「＜」が「≦」になっているのは，「極限操作」を思い浮かべてください．

*2:wikipedia:フィボナッチ数の中に，行列の漸化式があり，行列のべき乗計算を，RSAのときに話した手法を用いることで高速化できます．それによって，漸化式に基づいて $F_3, F_4, ..., F_n$ の順に求めるよりも，効率良くなります．

わさっきhb

大学（教育研究）とか，親馬鹿とか，和歌山とか，とか，とか．