こんにちは、Progate で新規事業開発のテックリードをしている 島津(@MakotoShimazu) です。
この4月に入社してから半年以上経ち、重い腰をあげてようやく Progate のテックブログデビューしました。皆さんよろしくおねがいします。
※ 本記事は Progate Advent Calendar 3日目の記事になります。
はじめに
計算量といえば、少し前にちょっとした話題になったのを覚えている方も多いのではないでしょうか。
100日後に退職する47歳
— 元アプリ開発者47歳@100日後に退職する47歳 (@tome_ura) 2021年10月13日
90日目#100日後に退職する47歳 pic.twitter.com/QqVgmonX7q
しかし、学生さんなどに実際に計算量を数えてもらおうとすると、しばしば何を数えればよいのかわからない、つまり「1」の決め方で混乱している人を見かけます。
そこで本記事では、時間計算量における「1」とは何者なのかを振り返ってみようと思います。 (そして、もしやる気がでたら、もう一歩踏み込んで実際のコードを見ながら「1」の時間について考えてみようと思います。)
計算量の定義
時間計算量は、ある処理における計算時間を見積もるための値です。
Time complexity - Wikipedia なんかを見てみると、以下のように書いてあります。
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.
--
時間計算量は通常、各基本的な操作は定数時間かかると仮定して、あるアルゴリズムを実行したときの基本的な操作の数を数えることで見積もられます。(筆者訳)
しかし、ここで言う「基本的な操作」とはどういった処理のことを言うのでしょうか。 僕がこれを書きながらパッと思いついたアイデアとしては以下のようなものがあります。
- コードの行数*1
- ループを回る数
- 処理中の四則演算の数
- CPUの実行する命令数
何を数えればよいのでしょうか?
基本的な操作を数えてみよう
結論から言うと、基本的にどれを数えても変わらないことが多いです。 なぜそうなるかを例をあげて紹介します。
たとえば、以下のようなコードの計算量について考えてみましょう。
int sum(int arr[], int n) { int acc = 0; for (int i = 0; i < n; ++i) { acc += arr[i]; printf("%d\n", acc); } return acc; }
ここではarr
とn
が変数として扱われているので、計算量を見積もるときにもこれらは変数として扱います。
行数
たとえばコードの行数であれば、以下のようになりそうです。
int sum(int arr[], int n) { int acc = 0; // 1行 // ループで回る部分1行 for (int i = 0; i < n; ++i) { // ループ内は2行 acc += arr[i]; printf("%d\n", acc); } // ループ総計: 3行 * n回 で 3*n 行 return acc; // 1行 }
つまり、行数で言えば 3*n + 2
ですね。
ループの数
ループを回る数については、 n
であることに疑問を持つ方は少なそうです。
四則演算の数
次に、四則演算の数はどうでしょうか。
考えようとすると、printf
をどう扱うかで悩まれるかもしれません。
++i acc += arr[i] printf() でなにかやっているのでいくつかは使っていそう・・・?
しかし、これは妥当な疑問でしょう。なぜなら、++i
や acc += arr[i]
よりも printf()
のほうが処理として重いことが想定されるからです。
そこで、新たな定数 C を適当に導入しちゃいましょう。
++i: 1個の足し算 acc += arr[i]: 1個の足し算 printf() : C個の四則演算くらいの重さの処理
こうすれば、中身を知らなくても計算量を求めることができます。
※なお、ここでは printf()
は今回変数として置いた arr
や n
の中身に依らず、一定の回数だけ四則演算をしていると仮定しています*2。このような前提が崩れるケースでは、定数を置くことはできないことに注意してください。
int sum(int arr[], int n) { int acc = 0; // 0回 // ループで回る部分1回 for (int i = 0; i < n; ++i) { // ループ内は 1 + C 回 acc += arr[i]; printf("%d\n", acc); } // ループ総計:1 + (1 + C)回 * n で (C+2)*n 回 return acc; // 0回 }
ということで、合計は (C+2) * n
回となりました。
CPU の命令数
面倒なんですが、四則演算と同様にやっていきましょう。 今回は、命令数を調べるのは面倒なので全部適当な定数を起きましょう。定数を置く際の注意点は先述の通りです。
int sum(int arr[], int n) { int acc = 0; // C_0 命令 // ループで回る部分C_l1回 for (int i = 0; i < n; ++i) { acc += arr[i]; // C_l2 printf("%d\n", acc); // C_l3 } // ループ総計:(C_l1 + C_l2 + C_l3) * n 命令 return acc; // C_1 命令 }
定数が多くてややこしいですが、全部足すとこんな感じですね。
C_0 + C_1 + (C_l1 + C_l2 + C_l3) * n 命令
「どれでもだいたい同じ」を定義する
いやーおつかれさまでした。 さて、ここまでの計算結果をまとめてみましょう。
- コードの行数: 3 * n + 2 行 - ループの数: n 回 - 四則演算の数:(C + 2) * n 回 - CPUの命令数:C_0 + C_1 + (C_l1 + C_l2 + C_l3) * n 命令
しかし、こんなことを毎回考えていると大変ですし、比べるのも難しいです。
たとえば、このアルゴリズムは四則演算が (C + 2) * n
だけど、このアルゴリズムは四則演算が (D * 2 + 4) * n + 10
です!と言われてもよくわからないですよね。
そこで、「大体同じくらいかどうか」を簡単に比較できるようにするために、よく知られるランダウの記号というものを導入してみましょう。
ランダウの記号の定義の確認
ランダウの記号は、計算量がある変数に対してどんな感じのグラフになるかを大まかに分類するために便利な手法です。
Wikipediaを参照すると細かく説明が書いてあるので、分かる人はこっちを読んでください。
また、このあたりは他にも説明している人はたくさんいるので、ここではいくつか例を出すだけに留めることにします。
例:
- O(10 * n^2 + 10000 * n + 1) = O(n^2) (各変数に関して、一番大きい乗数のみを残す感じ) - O(n + 4000 * log(n)) = O(n) (log(n)よりnのほうが"伸びが早い"ので、定数がいくら大きくてもnのほうが強い) - O(3^n + 10000000 * n^10) = O(3^n) (n乗はnの定数乗に比べてめっちゃでかい)
基本的に、変数のうち、一番大きくなる項について、定数を省いて記述するものだと考えておくとだいたい合っているかなと思います。
ランダウの記号を適用する
さて、頑張って求めた各指標に関して、このランダウの記号を適用してみましょう。
各指標の数字は以下のようなものでした。
- コードの行数: 3 * n + 2 行 - ループの数: n 回 - 四則演算の数:(C + 2) * n 回 - CPUの命令数:C_0 + C_1 + (C_l1 + C_l2 + C_l3) * n 命令
それぞれにランダウの記号を適用し、変数である n
に関して注目すると、以下のようになります。
- コードの行数: O(3*n + 2) = O(n) 行 - ループの数: O(n) = O(n) 回 - 四則演算の数:(C + 2) * n = O(n) 回 - CPUの命令数:C_0 + C_1 + (C_l1 + C_l2 + C_l3) * n = O(n) 命令
すべて O(n)
になりましたね!
ここで、再度時間計算量の説明に戻ってみましょう。
時間計算量は通常、各基本的な操作は定数時間かかると仮定して、あるアルゴリズムを実行したときの基本的な操作の数を数えることで見積もられます。(筆者訳)
ランダウの記号を用いることで、定数部分にとらわれず、「計算時間は変数(今回であれば n
)に対してどれくらいの強さで伸びるか?」という点に注目することができます。
つまり、単位は異なれど、コードの行数、ループの数、四則演算の数、CPUの命令数のどれを「基本的な操作」として扱っても「1」あたりにかかる時間は定数であり、変数である n
に対してランダウの記号を適用すればどの指標を使っても同じ結果を求めることができます。
まとめ
本記事では、計算量の数え方について触れ、結構雑でも変数と定数をちゃんと切り分けられていれば「1」として数えて良いということがわかりました。
しかし実際に実行時間を考えようとすると定数が大事になってくるため、時間計算量だけではなく、どれくらいの計算時間なのかということも頭に置いておく必要があります。 もし元気があったらこのあたりの定数に関して続きを書くかもしれないので、是非いいね・RT・はてブなどで僕にやる気をください。
次回は来週月曜日公開の、フロントエンジニアの平川さんより、 API クライアント・型生成スクリプトを高速化して DX 改善した話です。地道な改善が日々を幸せにするいい話、ぜひご覧ください!
最後になりましたが Progate では今絶賛採用活動中です。やりたいことはたくさんありますので、興味を持っていただいた方はまずはカジュアル面談からでもぜひご応募下さい!٩( ’ω’ )و