データ構造その1(計算量)

年の瀬になりました。データ構造第一回は計算量です。1回目2回目は短めのイントロみたいな感じ記事で、それ以降個別のデータ構造の話になります。今回の話は個別の構造から参照される形になる予定です。

計算量はメインではAnalysis of Algorithmsとかアルゴリズムの授業でやったりしますが、データ構造でも、どのオペレーションでどの構造が効率的かを語る上で必要になります。"めっちゃ速い", "なんか遅い気がする"とかは理系の言語ではないし、動かしてみて確認とかは物理じゃないんだから、という感じです。結構文系やりがちなのが動かしてみて速さをはかったりしますが、今のPCは基本的にマルチタスクでOSが勝手通信してたりして、nタイミングによって差が出たりします。CPUタイムと実際の時間が違ったりするので、理論上の数値が出せないと再現性がない(回数を増やすと理論値に近づくはず)という事になります。

ランダウの記号

で、計算量を表すのにはランダウの記号というものを使います。

ランダウの記号 - Wikipedia

ランダウの記号ではビッグオーO(n), ビッグシータΘ(n)、ビッグオメガω(n)が主に使われますが、基本的にデータ構造ではビッグオーを使うことが多いです。結構細かいとこまで見ると混乱します。nを与えられた要素の数として(例えば学生の数＝数学の点数の数とか)、$${O(n) = O(n^2)}$$なのに$${O(n^2)≠O(n)}$$だったりします。右辺で上界から押さえ込まれるという表現なので、$${O(n)}$$は$${O(n^2)}$$を超えないという感じです。逆にして成り立ったら、その世界は捻じれてますね。厳密に未満は小文字で$${o(n^2)}$$と書いたりしますが、細かい用法はアルゴリズムの回で書きます。データ構造の説明でのビッグオーはf(n)のnの数に応じてメインの処理がどれくらい行われるか、というものを表現します。

例えば、ソートで言うと、配列を端から舐めていって一番小さい数字を先頭に持ってきて、という選択ソートは最初にn個の数値をn-1回比較して(3個あったら2回の比較で最小が見つかる)、最小を取り、すでに最小が見つかっているので、それを除いたn-1個で一番小さい数値を探して、を繰り返すとn+(n-1)+…1回の比較となり$${\frac{(n-1)((n-1)+1)}{2}=\frac{n^2-n}{2}}$$となります。nが1兆とかはるかに大きくなった場合、$${n}$$は$${n^2}$$と比較した場合誤差と言えるくらい小さくなるので、そういう状況を$${n^2}$$が支配的と言い、$${O(n^2)}$$として表現します。簡単に言ってしまうと一番次数が大きいもので代表して書く感じです。なので各項を見て、支配的な項を係数を消して代表させる、ということですね。係数に関しては$${2n^3}$$も$${10n^3}$$もnが大きいと大差なくなる($${n^3}$$に近づいていく)ということです。
また、常に一発で答えが決まる場合O(1)と表します。

例えば、$${2x^2+1000x+123456789=O(x^2)}$$です。xが小さい場合、特に0の場合は処理回数は123456789(固定)になるのですが、計算量としては大量に計算した場合にどこに収束するか、という感じなので、個別の特にxが小さい場合を取りあげて計算量を語ることはあまりないです。逆に実際の現場では計算量が少ない方が速いとは限らないので、nが十分に大きくなるか、大きくなる可能性があるか、ということは考慮すべきかもしれません。場合によっては可読性が落ちるだけなので。とはいえ、たいていの言語で単純な処理は最適化されてnが小さい場合も高速で動くように書かれた標準ライブラリが用意されていたりもします。

単純なnのi乗だけでなく、$${log(n)}$$もよく出てきます。特に木構造で、2つに分岐していく場合、一番下の層がn個あると、その上の層は$${n/2}$$個になります。上から考えた方が楽なら、1個の下に2個分かれて、2個がそれぞれ2個に分かれると計4個に、と層ができます。バランスの取れた二分木だと、一番上から一番下まで下るのにかかる回数はlog(n)です。ちなみにコンピュータサイエンスでlogは2進数と相性のいいlog2(2の何乗か)を省略してlogと書くことが多いです。書籍によってlgと書いてるものもありますね。さらに同じサイズの木がm個あれば$${m log(n)}$$ですし、他にも組み合わせの問題は$${O(C^n)}$$になってきます。

計算量がわかってると競技プログラミングとかも強くなりますね。$${n^8}$$辺りになるとTLE出るので、そこに抑える工夫が必要になります。

練習問題

ちょっとアルゴリズム的な問題になってしまいますが、慣れるために、次の疑似コードの計算量を答えて下さい。 func() を呼んだ回数が答えです。

# 1.
for (i = 0; i < n; ++i) {
  func();
}

# 2.
for (i = 0; i < n; ++i) {
  for (j = i; j < n; ++j) {
    func();
  }
}

# 3.
for (i = 0; i * i < n; ++i) {
  func();
}

# 4.
for (i = n; i > 0; i /= 2) {
  func();
} 

アルゴリズムで出てくる問題(現状解けなくてOK)

# 5.
func(n) {
  if n < 2 {
    return n;
  }
  return func(n - 2) + func(n - 1);
}

欲しいものリスト

この下は執筆を応援してくれる人向けなので、興味なければ記事終了なので閉じてOKです。

Amazon欲しいものリストを作りました。
ギフトだけでなく、勉強で自分で買う書籍の参考にもどうぞ。
と言っても名著はたいてい読んでいるのでマニアックです。

サポートチャリーンは何に使われたかわからず、あまり気持ち良いものじゃないかも知れないので、こちらも設けました。基本的にここの月額に消えるくらいのサポートではありましたが(あと数か月分は頂いています、感謝です)。

基本的にお金をもらうなら払う人の意思を次につなげたいので、欲しいものリスト、ギフト頂いた場合、こちらで関連テーマを取り上げたいと思います。こういう話興味ある、と伝わる感じです。まぁ、技術記事期待されてるのかわかりませんが、その本を持ってる前提での解説記事とかだと、面白そうだけど理解できるかわからない、みたいな本をギフトに頂けると、一緒に読み進めて学ぶきっかけになるかな、と。できればそんな感じで進めたい。

こちらも執筆テーマになるので、良い循環になるかな、と思います。ギフトくれたのに書かない、とか書く書く詐欺なら晒してもらって構わないです(匿名だけど)。複数頂いたら、基本リストにして優先順位して書くと思います。筆不精がそれで尻叩かれるかもですね。

Amazonほしい物リストを一緒に編集しましょう

では、良いクリスマスを！