kantablog Written by Kanta Nakamura

【初心者向け】ビック・オー記法のおすすめ例題10選まとめ【解説付き】

Algorithm PROGRAMMING

本記事では、ビック・オー記法の習得のための例題として、おすすめ例題を10個をまとめ、それぞれ解説をします。

ビック・オー記法をもう一度見直したい人は、「【完全初心者向け】ビック・オー記法(Big O)とは何かを徹底解説してみる【例題あり】」を読めばokです。

なお、本記事では「世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法」より、一部抜粋しています。

ビック・オー記法のおすすめ例題10選まとめ

time

ここでは、おすすめ例題を10個をまとめました。
なお、答えは次のチャプターでまとめて解説しています。

問1

次のコードの実行時間はなんでしょう?

example1_bigO

答えをみる

問2

次のコードの実行時間はなんでしょう?

example2_bigO

答えをみる

問3

次のコードの実行時間はなんでしょう?

example3_bigO

答えをみる

問4

次のコードの実行時間はなんでしょう?

example4_bigO

答えをみる

問5

次のコードの実行時間はなんでしょう?

example5_bigO

答えをみる

問6

次のコードの実行時間はなんでしょう?

example10_bigO

答えをみる

ヒント: 上記のアルゴリズムは、ある数についてそれよりも小さい数で割り切れるかを調べることで、その数が素数であるかどうかを調べます。ある数nについて、nの平方根より大きな数で割れるとすれば、必ずよれよりも小さい数で割ることができますので、試し割りを行うのはnの平方根までで十分です。

問7

次のコードはn!(nの階乗)を計算します。
このコードの時間計算量はなんでしょうか?

example11_bigO

答えをみる

問8

次のコードは、0からn番目までのすべてのフィボナッチ数を表示します。
時間計算量はなんでしょう?

example14_bigO

答えをみる

問9

次の関数は、nまでの2のべき乗を表示します。
実行時間はどうなるでしょうか?

example16_bigO

答えをみる

問10

次のコードは、a % b(aをbで割ったあまり)を計算しています。
実行時間はなんでしょう?

practice3_bigO

答えをみる

解き方解説

それでは、答えと考え方を解説していきます。

問1

example1_bigO

実行時間は、O(N)です。

arrayという配列を2回ループしていますが、1つ目のループが終わったあとに、2つ目のループをしているので、O(N + N) = O(2N) = O(N)となります。

問2

example2_bigO

実行時間は、O(N^2)です。

arrayという配列を2回ループしていますが、1つ目のループの要素が実行されるたびに、2つ目のループが実行されているので、O(N * N) = O(N^2)となります。

問3

example3_bigO

実行時間は、O(N^2)です。

簡単な考え方として、ループ回数の平均を考えることで、答えを導き出すことができます。

外側のループが、N回繰り返されていることはわかりますよね。
では、内側のループはどうでしょうか?

内側のループの回数は変化しているので、平均を考えてみましょう。
考えてみると、1,2,3,4,5,6,7,8,9,10となっており、これらの平均は、だいたい5だという予測ができます。

つまり、外側N * 内側N/2 = O(N^2/2)、1/2は定数なので、答えは、O(N^2)と考えることができます。

問4

example4_bigO

実行時間は、O(ab)です。

配列Aの各要素に対して、内側のループは配列Bの長さ分だけ繰り返し処理を行っています。つまり、配列Aのサイズをa、配列Bのサイズをbとすると、O(a * b) = O(ab)となります。

内側のforループ内にあるif分は、定数時間で実行できるためO(1)となり、影響の少ない項となるので、問題はありません。

問5

example5_bigO

実行時間は、O(ab)です。

問4と似ていますが、if文がforループに代わっています。
では、このケースはどうなるのか?

一番内側のforループは100000回繰り返されます。つまり、O(a * b * 100000) = O(100000ab)となるわけですが、100000は定数なので、切り捨てられ、最終的な答えは、O(ab)となります。

問6

example10_bigO

実行時間は、O(√n)です。

間違えた人も多いかもしれませんが、注意深く考えれば簡単に解くことができます。

ループ内のif文はO(1)つまり定数時間なので、無視をします。
ループを見てみると、x=2から始まり、x * x = nで終了します。

つまり、xが√n(nの平方根)に達したときにループが終了すると言い換えることができるので、forループは√n回繰り返されると考えて、答えは、O(√n)となるわけです。

問7

example11_bigO

実行時間は、O(n)です。

elseの部分で、factorial(n-1)となっているので、このコードは、n,n-1,n-2,….,1のように、nの値が1ずつ減少しながら、0になるまで繰り返されるだけなので、O(n)となります。

問8

example14_bigO

実行時間は、O(2^n)です。

fib(n)がO(2^n)でそれがn回繰り返されているから、O(n2^n)と考えてしまいがちですが、本当にそれが正解でしょうか?

fib(n)を詳しく見てみると、fib(n)のnの値は、毎回変化しているので、次のように考えることができます。
2^1 + 2^2 + 2^3 + 2^4 + ... + 2^n
上記の合計は、2^n+1になるので、このコードの実行時間は、O (2^N)になります。

問9

example16_bigO

実行時間は、O(log n)です。

これは、このコードが何をしているのか考えることが答えを簡単に出すことができます。

上記のコードは、nを2で割り続けて、1になるまで繰り返しているので、nを2で割り続けたときに何回で1になるかが答えになります。nを1になるまで2で割り続ける回数は、O(log n)と表すことができるので、これが答えになります。

問10

practice3_bigO

実行時間は、O(1)です。

このコードは、定数時間で計算できるので、答えはO(1)になります。

これで、ビック・オー記法おすすめ例題10問すべての解説が終わりました。
お疲れ様でした😌

実際に解いてみて、知識が抜けているところがあった人は、「【完全初心者向け】ビック・オー記法(Big O)とは何かを徹底解説してみる【例題あり】」をみて復習してみてください。

今回は、これで終わりになります。
ありがとうございました。

参考文献

本記事で使用したコードは、下記の本から一部抜粋しました。
僕もアルゴリズムの勉強に使用した良本です。