競プロで学んだ計算量を業務でも気にしたいという話

はじめに

AIシステム部のS.Kと申します。
今回はAtCoderで水色まで到達した身として、さまざまな場面で役に立つ計算量についてまとめていこうと思います。

計算量という概念はアプリケーションに必要な計算リソースを見積もるのに便利な道具です。従量課金制のクラウドサービスが主流になっているこの世の中で、必要な計算リソースを意識するのはとても重要です。

また、AtCoderをしていると、嫌でも計算時間を気にする必要があります。基本的に1回の実行に対して実行時間は2秒までという制限があるからです。自分が書いたソースコードの実行時間が2秒程度で収まるのか、計算量を考えるとおおよその見積もりが立ちます。

アルゴリズムの性能を測る上で避けては通れないキーワード「計算量」について、可能な限り分かりやすく解説できればと思います。

計算量って何？

そもそも計算量とはなんでしょうか？
計算量という概念は主に計算複雑性理論で使われる言葉です。計算複雑性理論のWikipediaではこんな記載がありました。

以下引用

アルゴリズムの計算量（けいさんりょう）とは、計算機がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムのスケーラビリティを示す。形式的には計算機をチューリング機械やランダムアクセス機械（random access machine）などの計算モデルとして定式化したうえで、アルゴリズムの使用する資源の量を入力データ長などに対する関数として表す。計算モデルの瑣末な詳細に影響を受けないよう、計算量はその漸近的な挙動のみに注目し、定数倍を無視するO記法で書き表すことが多い。

えーーっと……？

よく分からないのでコトバンクの「計算量とは」のページを見てみましょう。

以下引用

世界大百科事典 第２版「計算量」の解説 けいさんりょう【計算量 computatinal complexity】 アルゴリズムの計算効率や問題の難しさを測るための尺度。主なものに，時間効率を測るための時間計算量，メモリー効率を測るための領域計算量などがある。他にも，計算回路の性能を議論するための計算量や，分散処理でのプロセス間の通信効率を測るための計算量など，用途に応じてさまざまな計算量が用いられている。　コンピューターで仕事を処理したり問題を解く場合，計算手順(アルゴリズム)の善し悪しで，プログラムの計算時間や使用する記憶容量が大幅に異なってくることが多い。

少し分かってきました。まとめてみると、計算量とはこういう概念です。

• 計算量の代表的なものとして、時間計算量と領域計算量(空間計算量とも言う)がある。
  • 計算手順の良し悪しで、必要な計算時間や記憶容量が異なる。
• 時間効率を測るのに時間計算量が用いられる。
• メモリー効率を測るのに領域計算量が用いられる。
• 他にも用途に応じてさまざまな計算量が用いられている。

すなわち、以下の二つのことが言えます。

• 時間計算量が小さい→計算時間が短い
• 領域計算量が小さい→必要な記憶領域(メモリ量)が少ない

なので基本的に「計算量が小さければ小さいほど、いいアルゴリズムである」と言っていいでしょう。

計算量の記述方法「ランダウの記号」とその意味

計算量を記述する方法として「ランダウの記号（参考:Wikipedia）」が用いられます。\(O\)という記号を使った、このような記述方法です。

このアルゴリズムの時間計算量は、入力とするデータの個数を\(n\)とした時、\(O(n)\)である。

「\(O(n)\)」の部分は「オーダー \(n\)」と読みます。これの意味は「このアルゴリズムの時間計算量は、入力とするデータの個数に(\(n\)に)比例する。」という意味です。言い換えると、「データの個数(\(n)\)が倍になると、計算時間も倍になる」という意味になります。
このカッコの中身は、任意の\(n\)についての関数が入ります。具体例を見てみましょう。

• 時間計算量が\(O(n^2)\)
  • 時間計算量は\(n\)の2乗に比例する。つまり、\(n\)が2倍になると計算時間が4倍になる。
  • \(n\)が増加すると、計算量が\(O(n)\)のアルゴリズムよりも計算時間が長くなりやすい。
• 時間計算量が\(O(\log(n))\)
  • 時間計算量は\(log n\)に比例する。つまり、\(n\)が2倍になると計算時間は\(log2\)増加する。
  • \(n\)が増加しても、計算時間は少しずつしか長くならない。
• 時間計算量が\(O(2^n)\)
  • 時間計算量は\(2^n\)に比例する。つまり、\(n\)が2倍になると、計算時間が\(2^n\)倍になる。
  • \(n\)が少しでも増加すると、計算時間がとても長くなる。
• 時間計算量が\(O(c)\) （cは実定数とする。）
  • 時間計算量は常に一定である。つまり、\(n\)が増加しても計算時間は変化しない。

つまり、この記述が表すのは「データ量 \(n\) が増加(減少)した時、処理時間がどの程度増加(減少)するか」なのです。計算量が空間計算量の場合は、「データ量 \(n\) が増加(減少)した時、処理に必要する記憶領域がどの程度増加(減少)するか」を表すことになります。

計算量が\(O(log n)\)であれば、データ量が増えるとしても、計算時間はそこまで長くならないので対して心配する必要はありません。しかし計算量が\(O(2^n)\)であれば、少しでもデータ量が増えると、計算時間がとても長くなってしまう、ということが分かりますね。

この様に計算量は何か基準となる変数(上記の場合は\(n)\)を決めて、それを使って記述します。\(n\)の取り方は他にも以下の例があるでしょう。

• 入力が文字列\(S\)の時、文字列\(S\)の長さ(文字数)
• 入力が整数\(N\)の時、\(N\)そのもの
  • \(N = 2^n\)と表した時の\(n\)、(すなわち\(log N\))を基準とすることも多いです。
• 入力がグラフ構造を持つとき、その頂点の数。

色々書きましたが、ここでは、「\(O(n)\) （オーダー \(n\) ）ってそういう意味なのか！！」というのが伝われば大丈夫です。そして「\(n\)について増加しやすければしやすいほど、計算量が大きい」ということに気を付けましょう。

詳しい数学的な定義が気になる方は、ランダウの記号のWikipediaに十分な記述がありますので、目を通していただければと思います。

計算量の求め方

では、具体的な計算量の求め方を見てみましょう。今回は時間計算量に焦点を当ててみようと思います。

以下のPythonのソースコードを見てください。

cnt = 0
for x in range(n):
    for y in range(n):
        for z in range(n):
            if x + y + z == w:
                cnt += 1
print(cnt)

このソースでは0以上\(n\)未満の整数3つの組み合わせで、その和がwになるものがいくつあるかを計算しています。このソースの計算量は\(O(n^3)\)になります。
この計算量になる理由は、「【x+y+zがwと一致しているか】を確かめる演算を合計で\(n^3\)回するから」です。forループの中の演算が何回行われるかを数えればいい訳ですね。

では次のコードを見てみましょう。

cnt = 0
for x in range(n):
    for y in range(n):
        if 0 <= w - x - y < n:
            cnt += 1
print(cnt)

これは1つ前のコードと全く同じ結果を出力します。wと、2つの整数の和の差が0以上 \(n\) 未満であれば、整数3つの組み合わせで、その和がwになるものが存在するからです。
このソースの計算量は\(O(n^2)\)になります。「【w-x-yが0以上、\(n\)未満であるか】を確かめる演算を合計で\(n^2\)回するから」が理由です。

計算量を求める場合はこのように、「演算を行う回数を\(n\)を用いて記述した式」を考えればよい訳です。これを考えることで、\(n\)が増加すると計算時間がどの程度長くなるのかが分かる、という訳ですね。

こうして計算量を考えることで、「処理の内容が同じだとしても、記述の仕方で処理速度がどの程度変化するか」を定量的に把握することができるのです。

ライブラリを利用する場合

現在のアプリケーション開発において、ライブラリの利用は不可欠なものです。そうなった時、アプリケーション全体の計算量を見積もるためには、ライブラリで提供されている関数や、クラスのメソッドの計算量を把握しておく必要があります。
これに関しては以下の対応が必要かと思います。

• ドキュメントから仕様を確認する。
  • どのような処理を行っているのかドキュメントを確認し、その処理に必要な計算量を見積もる。
  • 場合によっては計算量そのものの記載がある。
  • ドキュメントのみからでは正確な見積もりができない場合もある。
• 実際のソースコードを読み込む。
  • 上記の手法で計算量を見積もる。
  • かなり正確な見積もりができるものの、ドキュメントを読むよりも時間がかかることが想定される。

どこまで正確な見積もりが必要になるかは、ケースバイケースだと思います。実際に実行した時の処理時間を計測した方が有効な場合もあるかと思います。

業務での計算量

例えば、Webアプリの計算量(時間計算量、空間計算量の両方)を小さくすると、以下のメリットがあるかと思います。

• バックエンドでの計算量が小さい時
  • ユーザーの待ち時間が短くなる。
  • 処理時間に対して従量課金がある時、利用料金が安く済む。
  • 使用したメモリに対して従量課金がある時、利用料金が安く済む。
• フロントエンドでの処理時間
  • ユーザーのPCにかかる負荷が軽減される。
  • UI/UX改善に繋がる。
    • フロント側の処理が重くても待ち時間の増加に繋がります。

以下のような場合は特に、より正確な計算量の確認が重要でしょう。

• 処理で取り扱うデータの量が膨大なとき。
• 計算リソースに制限があるとき。

「どの処理について」の計算量を考えるか

先ほどは時間計算量を比較演算の回数で見積もりました。しかし、どの処理の回数を基準として計算量を見積もるかは場合によって変わると思います。以下のような処理の回数はとても重要です。

• 外部との通信の回数と容量
  • 回数や容量が多いことは、帯域の圧迫であったり、余計な費用増加に繋がります。
  • API等を利用する際は、APIの呼び出し回数に制限がある場合もあります。
• DBにアクセスする処理の回数
  • 回数が多いとDBの負荷が増加します。
  • クエリ回数に対して課金があるDBサービスもあるかと思います。
• パスワードやトークン、秘密鍵といった機密情報が必要な処理の回数
  • 特定のソースコードというよりかは、システム全体の設計で意識することかと思います。

計算量を定義する際に、「他にも用途に応じてさまざまな計算量が用いられている。」と述べたのはこれが理由です。「上記の処理の回数を少なくすることで、処理時間が短くなる」という訳ではないこともあると思います。計算時間を短くすることを優先するべきなのか、はたまたDBの負荷を減らすべきなのか。
システムの仕様や要件と相談する必要があるかと思います。

計算量は常に考えるべきなのか

ここまで計算量を小さくして、処理を効率化することばかり論じてきましたが、計算量をあまり気にしなくていいケースもあります。

• データの量や長さが固定、あるいは少ないとき
• システムの仕様上どうしてもその処理が必要なとき

この様な場合は計算量が多少多くなっても問題ないかと思います。

なぜこのような場合をわざわざ論じたかと言うと、計算量を小さくすることで以下の問題が生じる可能性があるからです。

• 処理内容の無駄を極力省いた結果、他者がそのソースコードを読んだ時に、どんな処理が行われているのかが分からない。
• 特定の処理を効率よく行うことに特化するあまり、再利用性が損なわれてしまう。
• 効率がよいコードを書こうとするあまり、コーディングにかかる時間が長くなってしまう。

これらの問題から、常に計算量を小さくするべきとは単純に断ずることができない部分があります。システムの要件や仕様、場合によっては納期も考慮した上で、どのような実装を行うべきなのか判断するべきです。

AtCoderにおける計算量

この章は競プロに取り組もうと思っている方向けです。

AtCoderにおいて意識するべき数字があります。それは\(O(10^8)\)という数字です。

AtCoderでは、実行時間が2秒に制限されています。これを超えないためには\(O(10^8)\)あたりが限度だということです。これを超えたアルゴリズムはTLE（実行時間制限オーバー）になる場合が多いです。

入力が長さNの配列として与えられる場合を考えてみましょう。
AtCoderにおいては、Nの最大値が制約として与えられています。そのため、それぞれの制約に対して、「これくらいの計算量ならTLEにならない」という目安を書いておきます。

• \(N\)が最大で\(10^2\)
  • \(O(N^3)\)のアルゴリズムを動かしても問題ないでしょう。
  • 多くの場合、特に計算量を減らす工夫をする必要もないかと思います。
• \(N\)が最大で\(10^3\)～\(10^4\)
  • \(O(N^2)\)あたりが限度でしょう。
• \(N\)が最大で\(10^5\)～\(10^6\)
  • \(O(N \log N)\) あたりが限度でしょう。
  • 一つ一つの処理が重い場合は\(O(N)\)にするべきかもしれません。
  • これはクイックソートの計算量にあたります。ソートができるのはこの辺りまでです。
  • 2重ループによる全探索は難しいです。
• \(N\)が最大で\(10^7\)~\(10^8\)
  • \(O(N)\)が限度でしょう。
• \(N\)が最大で\(10^9\)
  • \(O(N)\)で軽い処理ならギリギリTLEにならないでしょう。
    • そもそも入力に\(O(N)\)時間がどうあがいてもかかります。処理が軽ければ間に合うはずです。
  • \(O(\log N)\)や定数時間(\(N\)に依存しない時間)で処理が終わるものが理想です。

表にまとめるとこんな感じです。慣れてくるとこの表がなんとなく頭に入ると思います。

\(N\)の最大値	計算量	備考
\(10^2\)	\(O(N^3)\)	計算量を考慮する必要はほとんどない。
\(10^3\)～\(10^4\)	\(O(N^2)\)
\(10^5\)～\(10^6\)	\(O(N \log N)\)	クイックソートによってソートを行うことができる。
\(10^7\)～\(10^8\)	\(O(N)\)
\(10^9\)	\(O(\log N)\) 若しくは\(O(c)\)	処理が軽いのであれば\(O(N)\)でもいける可能性あり。

AtCoderでは、難易度が高いほど入力長の最大値が大きくなる場合が多いです。そのため実装に工夫や知識が必要になってきます。なのでAtCoderで上位になるためには、計算量(主に時間計算量)が小さくて済むアルゴリズムについて学び、それを実装する技術が必要です。

すなわち、優秀な色の持ち主はアルゴリズムに対する知識が深く、その応用方法を熟知しているという訳です。

まとめ

私は競プロや研究のために計算量について学びましたが、気がつくと常に意識するようになっていました。まずはなんとなくでもこれを理解し、できるだけ計算量が小さくなる実装を心がけることは大事だと思います。

計算量が小さくなるような実装を行うには、様々なアルゴリズムの知識が必要になることがあります。その知識が足りていなかったとしても、「これから書くプログラムの計算量、これくらいかな…？」と分かるだけで、相談することや、実際に動作させたときに何が起こるか想像することができます。

まずは「この処理の計算量はこれくらいかな…？」と考えるところから始めてみてはいかがでしょうか。