全部解けたらレッドコーダー!? #計算量解析クイズHARD
「GENUINEな競プロerにしかできない!計算量解析クイズ!!」(https://kuizy.net/quiz/147934)に触発されて、難しいやつを作りました。是非挑戦してみてください!!!
ビュー数3372平均正答率46.7%全問正解率4.0%
正答率などの反映は少し遅れることがあります。
1. 画像の計算量として、最も近いものを選んでください。
- Θ(N)
- Θ(NlogN)
- Θ(NloglogN)
たとえば、N=1024 の場合、計算回数は、
10*1 + 9*1 + 8*2 + 7*4 + 6*8 + 5*16 + 4*32 + ... + 1*512
となり、ほとんどの i に対して j のループが 1 回であることが分かります。
実際に、計算回数は定数部分まで見積もると 2N に収束します。(N が大きい場合)
2. 画像の計算量として、最も近いものを選んでください。
再帰関数を用いた問題になりますが、計算回数はフィボナッチ数列の第 N 項に比例します。したがって、計算量は O(1.618...^N) になります。なお、1.618... の値は「黄金数」と呼ばれています。
3. 画像の計算量として、最も近いものを選んでください。
- Θ(Nlog^2 N)
- Θ(NlogNloglogN)
- Θ(NlogN)
i が決まった時の j, k ループ内の計算量は O((N/i)log(N/i)) なので、全体の計算回数は O((N/1)log(N/1) + (N/2)log(N/2) + ... + (N/N)log(N/N)) であることが分かります。
そこで、N/x log (N/x) を 1 から N にかけて積分した値は (Nlog^2 N)/2 なので、答えは O(Nlog^2 N) です。
4. 画像の計算量として、最も近いものを選んでください。
合計計算回数は、N/sqrt(1) + N/sqrt(2) + ... + N/sqrt(N) であることが分かります。これは x を用いて N/sqrt(x) を 1 から N までの区間で積分した値に近くなります。
1/sqrt(x) の積分は sqrt(x) * 定数になるので、求める値は N*sqrt(N)*定数=O(N^1.5) になります。
5. 画像の計算量として、最も近いものを選んでください。
たとえば、N に 18 を入力しましょう。そうすると、18 は (9, 10) に分かれます。(9, 10) は (4, 5, 6) に分かれます。(4, 5, 6) は (2, 3, 4) に分かれます。… そのように、各階層につき最大で 3 つしか出現しません。したがって、計算量は 3 * logN = O(logN) です。
6. 画像の計算量として、最も近いものを選んでください。
2 進数の bit ごとに考えると、ある桁について「i のループで選ばれるか」「j のループで選ばれるか」「k のループで選ばれるか」「l のループで選ばれるか」「どれでも選ばれずに最後まで残るか」の 5 通りがあるので、計算量は O(5^N) です。
7. 画像の期待計算量として、最も近いものを選んでください。
※ただし、gcd は既に前計算されており O(1) で求められるものとします。
最大公約数が 1 でない確率は、最大公約数が 2の倍数, 3の倍数, 4の倍数, ..., Nの倍数、となる確率を考えて、1/4 + 1/9 + 1/16 + ... + 1/(N^2) = 0.6449... 以下になります。したがって、最大公約数が 1 である確率は 1-0.6449...=0.3551 以上になり、Nによらず定数時間であることが分かります。
8. 画像の計算量として、最も近いものを選んでください。
これはマージソートです。マージソートの計算量は O(NlogN) なので、答えは O(NlogN) です。
9. 画像の計算量として、最も近いものを選んでください。
- Θ(2^√N・√N)
- Θ(2^√N・N)
- Θ(2^√N)
各 x に対して、計算回数は 2^sqrt(x) になります。これを 1 から N に対して積分すると、O(2^sqrt(N) × sqrt(N)) のオーダーになるのです!!!
10. 画像の計算量として、最も近いものを選んでください。
- Θ(N^1.31)
- Θ(N^1.41)
- Θ(N^1.51)
計算量は、O(N^(log(7)/log(4))) = O(N^1.4036...) となります。これは多倍長演算の一つのアルゴリズムである「Toom-Cook-4 法」を単純化したものです。詳しい話はこちらの記事をお読みください。(https://qiita.com/square1001/items/1aa12e04934b6e749962)
全部解けたらレッドコーダー!? #計算量解析クイズHARD
0 / 10点
あなたの正答率は86.4%で、平均の46.7%よりも上です!
クイズをやり直す
都道府県のご当地クイズ
人気急上昇中
もっとクイズを見る