AtCoderのPython3で許されるループ回数

ループが何回くらいだと間に合うのか、10**10を超えるとダメそうなのはさすがにわかるのですが、ボーダーがどのへんなのかしょっちゅうわからなくなります。そこで軽く確認して覚えておくことにしました。

まずはローカル環境で次のテストを実行します。

n回の単純ループで、ループ内は加算を1回するだけの、およそO(n)の中でもっとも早く終わる部類であろうコードです。

def loop(n):
    ans=0
    for i in range(n):
        ans+=i
    return(ans)

for i in range(10):
    print("Testing for n = 10 ^", i)
    %timeit loop(10**i)

Testing for n = 10 ^ 0
350 ns ± 0.911 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
Testing for n = 10 ^ 1
814 ns ± 1.11 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
Testing for n = 10 ^ 2
3.73 µs ± 30.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Testing for n = 10 ^ 3
39 µs ± 103 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Testing for n = 10 ^ 4
404 µs ± 643 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Testing for n = 10 ^ 5
4.14 ms ± 5.28 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Testing for n = 10 ^ 6
42.2 ms ± 90.2 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Testing for n = 10 ^ 7
427 ms ± 860 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
Testing for n = 10 ^ 8
4.24 s ± 23.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Testing for n = 10 ^ 9
43.2 s ± 411 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

10⁸時点で2000msを超えていました。 AtCoderのコードテストに次のコードを投げ、上記の時間と大差ないかどうかを確認してみます。

def loop(n):
    ans=0
    for i in range(n):
        ans+=i
    return(ans)

loop(10**7)

終了コード 0
実行時間 609 ms
メモリ使用量 5484 kb

ローカルだと427 msだったので、3割くらい厳しくなりましたが、大きくは違わないですね。

結論

10⁷はきわどい、10⁸はアウト。10⁶以下は少し余裕アリ。