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