Big O 記法

こんにちは。開発担当のマットです。

僕はプログラミングが大好きです。パソコンに自由自在にコマンドを書いて、好きなものを作れることはとても面白くて、プログラマーになった理由です。
しかし、プログラムの書き方に気を付けないと、規模を拡大することに連れ、処理がカクカクと遅くなってしまうこともあります。

この記事にて、プログラマは常に気を付けなければならない Big O 記法を紹介したいと思います。

Big O 記法とは？

Big O 記法 (別名：オーダー記法、O-記法、ランダウの記号) はドイツの数論家であるポール・バッハマンによって1894年に、彼の著書『解析数論』(Analytische Zahlentheorie) の第二巻で初めて導入されました。これに触発されてエドムント・ランダウが1909年に発明しました。

「どういうもの？」かというと、何らかの関数(何らかの機能)の規模を大きくするに連れ、その関数の処理時間がどのように伸びるか、の表記と考えてもいいかもしれません。

実例で考えると？

ゲームの例で考えましょう・・・
特定のゲームではなく、たくさんのAIプレーヤが遊ぶ戦略ゲームとか、何でもいいです。

このゲームで、プレーヤーが順番に遊びます。
ゲームのメモリーに、プレイヤーの順番リストがあるとしましょう。
ゲームに4プレーヤーがいるとしましょう。

O(1)

では、ゲームの一番目のプレーヤーを見つけるのに、どれぐらい時間がかかりますでしょうか？プログラムがしないといけない処理は：
・まず、プレーヤーのリストを見る。
・リストの頭のプレーヤを引き出す。
・終わり。

簡単な処理ですね。さて、プレイヤー数をなんと 10,000人にしたら、その処理がどうなるでしょう？
・まず、プレーヤーのリストを見る。
・リストの頭のプレーヤを引き出す。
・終わり。

変わりませんよね。Big O 記法では、こういう関数を O(1) と書きます。
O(1) とは、定数時間。関数に突っ込むデータの規模が大きくなっても、処理時間が変わりません。

プログラムを書く時（特に、大規模のデータを処理するプログラム）、O(1)の関数ばっかりでできることは一番望ましいです。

O(n)

次、各プレーヤに100ポイントを与えましょう！
4人のプレイヤーがいる場合、
・まず、プレーヤー1に100ポイントを与える
・次、プレーヤー2に100ポイントを与える
・次、プレーヤー3に100ポイントを与える
・次、プレーヤー4に100ポイントを与える
・終わり。

簡単な処理ですが、10,000人プレーヤーがいるとしたら、その人数分の時間がかかりますよね。これは O(n) と書きます。
規模が大きくなるに連れ、その分遅くなります。データは2倍あるなら、処理は2倍遅い。

O(n²)

次、少し難しくなりますが、このゲームに「隠れ情報」があるとしましょう。
例えば、各プレーヤーの財産が自分にも、他人にも、見られないというルール。
もちろん見られませんが、賢いAIを作るには、自分と他プレーヤーの財産を推測する関数も作りたいですね。

・まず、プレーヤー1が自分の財産を推測する。
・次、プレーヤー1がプレーヤー2の財産を推測する。
・次、プレーヤー1がプレーヤー3の財産を推測する。
・次、プレーヤー1がプレーヤー4の財産を推測する。
・次、プレーヤー2がプレーヤー1の財産を推測する。
・次、プレーヤー2が自分の財産を推測する。
・次、プレーヤー2がプレーヤー3の財産を推測する。
・次、プレーヤー2がプレーヤー4の財産を推測する。
・次、プレーヤー3がプレーヤー1の財産を推測する。
・次、プレーヤー3がプレーヤー2の財産を推測する。
・次、プレーヤー3が自分の財産を推測する。
・次、プレーヤー3がプレーヤー4の財産を推測する。
・次、プレーヤー4がプレーヤー1の財産を推測する。
・次、プレーヤー4がプレーヤー2の財産を推測する。
・次、プレーヤー4がプレーヤー3の財産を推測する。
・次、プレーヤー4が自分の財産を推測する。

数えると、 4 プレーヤーで 16 ステップが必要です。
8プレーヤーだとしたら、64ステップが必要になります。

規模を2倍にすると、4倍の処理時間となりますね。
平方関係なので、O(n²) と書きます。

他にもありますか？

限りなく、他にもたくさんの表記があります。
O(n³) もありますし、 O((n-1)²)もあります。
O(log n)もありますし、恐ろしい O(n!) もあります。

まとめ

それぞれのBig O 記法の表記の意味を暗記する必要はありませんが、プログラマーとして、何かの関数や機能やアルゴリズムを作るとき、無駄に時間が掛かるやり方でやっていないか、気を付けなければならないと思います。

この Big O 記法を常に頭にいれて開発をすると、より速やかで優れているコードは書けると思いますので、今後もこの記法を覚えてプログラミングをやっていきたいと思います。