自分が書いたプログラムの実行になぜこんなに時間がかかるのか、不思議に思ったことはありませんか？もしかしたら、コードの効率を上げることができないかと考えているのかもしれません。コードがどのように実行されるかを理解することで，コードを次のレベルに引き上げることができます．Big-O表現は，コードの実際の効率性を計算するのに便利なツールです．

ビッグオー表記法は何ですか？

Big-O表現は、コードの実行にかかる時間を計算する方法を提供します。実際にコードを実行するのにかかる時間を計算することもできますが、この方法では小さな時間差を捉えることは困難です。例えば、20〜50行のコードを実行するのにかかる時間はごくわずかです。しかし、大規模なプロジェクトでは、こうした非効率が積み重なることもあります。

Big-O表現は、アルゴリズムの効率を測定するために、いくつのステップを実行しなければならないかを計算します。Big-O表現では、異なるアルゴリズムを実行するのに必要なステップ数で測定し、その効率を客観的に比較することができるようになる。

ビッグ・オー・シンボルの計算方法

引き出しの中に靴下が何足あるかを計算する関数を2つ考えてみよう。各関数は靴下のペア数を取得し、個々の靴下の数を返します。コードはPythonで書かれていますが、これはステップ数の計算方法に影響しません。

アルゴリズム 1.

def sockCounter(numberOfPairs): individualSocks = 0 for x in range(numberOfPairs): individualSocks = individualSocks + 2 return individualSocks

アルゴリズム 2.

def sockCounter(numberOfPairs): return numberOfPairs * 2

これは愚かな例であり、どのアルゴリズムがより効率的であるかは簡単に判断できるはずである。しかし、練習のために、それぞれのアルゴリズムを見てみよう。

関連：プログラミングにおける関数とは？

アルゴリズム1にはいくつかのステップがある。

1. 変数 individualSocks に 0 を代入している。
2. 変数iに値1を代入する。
3. iの値とnumberOfPairsを比較する。
4. 2つの独立した靴下を追加します。
5. 個々の靴下の付加価値を自分に分配するのです。
6. iを1つ増やす。
7. そして、ステップ3と6の間を(Individuals-1)と同じ回数だけ循環する。

アルゴリズム1について、完了しなければならないステップ数は次のように表すことができる。

4n + 2

4つのステップをn回クリアする必要があるのです。この場合、nはnumberOfPairsの値と等しくなる。また、一度に完了するステップも2つあります。

一方、Algorithm 2は1ステップのみで、numberOfPairsの値を2倍する。 こう言える。

1

もしまだ明らかでなかったなら、アルゴリズム2がどれだけ効率的であるかを簡単に見ることができます。

ビッグ・オー解析

アルゴリズムのBig-O表現に興味を持つ場合、全体の効率に関心があり、ステップサイズなどの細かい解析にはあまり関心がないことが多いようです。表現を簡単にするために、効率の大きさだけを述べればよい。

上記の例では、アルゴリズム2は次のように表現されます。

O(1)

ただし、アルゴリズム1は以下のように簡略化される。

O(n)

このスナップショットは、アルゴリズム1の効率がnの値にどのように関連しているかを示しています。数字が大きくなるほど、アルゴリズムはより多くのステップを必要とします。

リニアコード

nの値は分からないので、nの値が実行する必要のあるコードの量にどのように影響するかを考える方が有益である。アルゴリズム1では、この関係は線形であると言える。ステップ数とnの値をプロットすると、昇順の直線になる。

二次コード

すべての関係が線形の例のように単純なわけではありません。2次元の配列があり、その中の値を検索する場合を考えてみましょう。次のようなアルゴリズムを作ることができます。

def searchForValue(targetValue, arraySearched): foundTarget = False for x in arraySearched: for y in x: if(y == targetValue): foundTarget = True return foundTarget

この例では、ArraySearchdの配列の数と各配列の値の数によって、ステップ数が決まります。したがって、簡略化されたステップ数はn*nまたはn²となります。

この関係は2次関数的なものであり、このアルゴリズムのステップ数はnに対して指数関数的に増加することになる。Big-O表記では、次のように書けるだろう。

O(n²)

関連：CSSファイルのチェック、クリーニング、最適化に便利なツール群

デジタル用

他にも様々な関係がありますが、最後に紹介するのは対数の関係です。記憶を呼び起こすと、ある数の対数とは、与えられた底を持つ数に到達するために必要な指数の値である。例えば、こんな感じです。

log 2 (8) = 3

対数は3に等しい。底が2なら、8という数字を得るには3の指数値が必要だからだ。

したがって、対数関数と指数関数の関係は逆になる。nが増加するにつれて、アルゴリズムを実行するために必要な新しいステップの数は減少する。

一見、直感に反しているように見えます。アルゴリズムのステップサイズはどのようにしてnより遅く成長できるのでしょうか？バイナリサーチはその良い例です。一意な値の配列から数値を検索するアルゴリズムを考えてみましょう。

• ここでは、小さいものから大きいものまでの配列で検索を開始することにします。
• 次に、配列の真ん中にある値を調べます。
• 数値が高い場合は低い数値を、数値が低い場合は高い数値を検索対象から除外させていただきます。
• では、残りの数値のうち、真ん中の数字を見てみましょう。
• ここでも、目標値が中央値より上か下かで、半分の数字を除外することになる。
• ターゲットを見つけるまで、あるいはリストにないことが確認できるまで、この作業を続けます。

ご覧のように、2値探索では毎回取り得る値の半分を消去するため、nが大きくなっても配列のチェック回数にほとんど影響がありません。これをBig-Oの表現で表すと、次のようになる。

O(log(n))

ビッグ・オー・シンボルの重要性

Big-O nationは、アルゴリズムの効率性を迅速かつ簡単に伝える方法を提供します。これにより、異なるアルゴリズムを選択することが容易になります。これは、ライブラリからアルゴリズムを使用する際に、必ずしもそのコードがどのようなものであるかを知らない場合に便利である。

初めてコードを学ぶときは、一次関数から始めます。上の図を見ていただければわかるように、これでかなり前進することができます。しかし、経験を積み、より複雑なコードを構築するようになると、効率が問題になり始めます。コードの効率を数値化する方法を理解することで、コードの効率をチューニングし、アルゴリズムの長所と短所を比較検討するのに必要なツールを得ることができます。