以下のコードの計算量について伺いたいです

Question

質問内容

以下のコードの計算量を教えてください。Atcoder,ARC104-B問題です。
計算量はO(N^2)と判断しました。Nは最大でも5,000しかとらないと明言されているため、計算量は多く見積もっても10^8で収まると考えましたがTLEとなりました。

以下のコードの計算量を教えてください。
また、計算量に問題がないのであればどの部分で計算量が増大してしまったのかも併せて教えていただけると幸いです。

ソースコード

from operator import sub

N,S = input().split()

N = int(N)
ans = 0

codes = [[0,0,0,0]]

for i in range(N):
    codes.append(codes[i][:])
    if S[i] == "A":
        codes[i+1][0] += 1
    elif S[i] == "T":
        codes[i+1][1] += 1
    elif S[i] == "G":
        codes[i+1][2] += 1
    elif S[i] == "C":
        codes[i+1][3] += 1
tem = []

for i in range(N+1):
    for j in range(i+1,N+1):
        tem.append(list(map(sub,codes[j],codes[i])))

for l in tem:
    if l[0] == l[1] and l[2] == l[3]:
        ans += 1
        
print(ans)

試したこと

一番オーダーが大きい部分はi,jの二重ループでappendの計算量はO(1)のため、計算量はO(N^2)と判断しました。

補足情報

初めての質問ですので、何か失礼がありましたらご教示いただけると幸いです。

Answer 1

計算量はあってますが、純粋にPythonが遅いので時間がかかってるだけです。
ほかの人の提出を見ても無駄がない書き方をしてギリギリのようです。
C++のように早い言語ならこういう書き方でバグを減らすことも全然かまわないと思いますが、Pythonだとあらかじめ長さがわかってる配列をappendで構築する必要があるのかとか、そもそも配列が必要なのかを検討したほうがいいでしょう。

Comments

[inoino]

yudedako67さん
回答ありがとうございました。計算量はあっていたようで安心しました。もともとpythonは遅いということはわかっていましたが、ここまでとは思っておりませんでした。