計算量 - かに

計算量

計算量について、償却/期待/平均など / noshi91のメモ

できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 / rsk0315

間違えやすい計算量

素数の逆数和

$ O(\mathrm{loglog}N)

エラトステネスの篩の計算量は$ O(N\mathrm{loglog}N)

整数の逆数和（調和級数）

$ O(\mathrm{log}N)

長さ$ Nの数列を、$ 1から$ Nまでそれぞれの間隔で見ていく操作の計算量

code: ex.py

# O(NlogN)

for x in range(1, N):

for kx in range(x, N, x):

pass

割り算で出てくる項数

$ O(\sqrt{N})

$ Nを$ 1から$ Nまでの整数でそれぞれ割って小数点以下を切り捨てたとき、全部で何種類の整数が出てくるか

リファレンス

素数の逆数和は発散する / アルゴ式

調和級数などのはなし / ageprocpp(ka age)

#数学的考察