このコードの計算量はO(N^3)ですか？

Question

Python3 のコードです。

N = 100
A = [0]*N

cnt = 0
for i in range(N):
    for j in range(N):
        if i == j: continue

        left, right = min(i, j), max(i, j)
        M = len(A[left: right+1])

        for k in range(0, M, 2):
            cnt += 1

print(cnt)

上記のコードの全体の計算量は O(N^3)であってるでしょうか。

        for k in range(0, M, 2):

の部分の計算量が O(N) になると思うので、全体の計算量はO(N^3)だと思うのですが、あってるでしょうか。

Answer 1

はい、特に最適化などかけていなければ、ループはループのままなので、オーダーはO(N^3)です。

---

9/13追記：出力だけが目当てなら、次の式を使えば、O(1)にすることが可能です。

N = 100
cnt = ((N-1)*N*(N+7))//6 - (N*N)//4
print(cnt)

なぜこれで計算できるのかは、そこまで難しい話でもないので、投稿者さんの課題ということにしておきます。

Comments

[takey]

どちらかというと、cntの計算がしたいわけではなく、`for k in range(0, M, 2):` の部分の計算量の算出方法が知りたくて説明しました。そういう意味では、cntの計算をするようなコードの書き方が悪かったですね。（do_something()とかにすればよかったです）

Teratailに投稿したモチベとしてはまあ少なくとも当該コード部分はO(logN)じゃないだろうし、だったらO(N)かな。でも自信ないな。そうだTeratailで質問しようといった感じです。でも、ご回答ありがとうございました。