GENUINEな競プロerにしかできない #計算量解析クイズ!!
競技プログラミングの計算量解析をクイズにしてみました
ビュー数8961平均正答率71.1%全問正解率8.4%
正答率などの反映は少し遅れることがあります。
1. 画像の計算量は?
Θ(...)と書いているのはO(...)のことだと思っても構いません(厳密には違います)
3. 画像の計算量は?
√Nを切り上げた数に到達すると、このループは止まるので、Θ(√N)です
4. 画像の計算量は?
一回目のjに関するループはN回
二回目のjに関するループは[N/2]回
...
k回目のjに関するループは[N/k]回
...
N回目のjに関するループは[N/N]=1回
とループの回数が減りながら加算されるので
N/1+N/2+N/3+...+N/N=Θ(NlogN)となります
詳しくは調和級数で検索してみてください
5. 画像の計算量は?
bit全探索などでよく見る形です
1<<Nは2のN乗を表します
6. 画像の計算量は?
難問です
jはiに対してi&j==jとなる数のうち0以外全体を重複なくとります
よってΘ(3^N)になります
https://qiita.com/Euglenese/items/260f9ddf513f772d7e42
が詳しいです
7. 画像の計算量は?
- Θ(NloglogN)
- Θ(NlogN)
- Θ(N)
エラトステネスの篩と呼ばれるものです
N以下の全ての素数の逆数和はΘ(loglogN)であることが知られているので、
Θ(NloglogN)です
8. 画像の計算量は?
- Θ(NloglogN)
- Θ(NlogN)
- Θ(N)
あまり見る形では無いですが、小ネタとして出しました
全ての自然数の二乗の逆数和はなんと発散せず収束します
よってこの問題の計算量はΘ(N)です
詳しく知りたい方はバーゼル問題と調べると出てきます
GENUINEな競プロerにしかできない #計算量解析クイズ!!
0 / 8点
あなたの正答率は86.4%で、平均の71.1%よりも上です!
クイズをやり直す
都道府県のご当地クイズ
人気急上昇中
お絵描き診断
「死」の漢字を書いてわかるサイコパス度
もっとクイズを見る