Pythonコードの計算量オーダーの添削をお願いします

Question

先日のプログラミングコンテストに初めて提出したコードの復讐をするために、
計算量オーダーを算出したいと思っています。
以下のように計算したのですが、合っているかどうかの添削をお願いします。

count = 0
for i in range(n):
    for k in range(i+1,n+1):
        if sum(s[i:k]) == 0:
            count += 1

計算手順

まずif文を無視するとforの二重ループは
\sum_{k=1}^{n}k = \frac {1}{2}n(n-1)
という風に計算できるので、
1/2 * O(n^2 + n) = O(n^2)
となります。

(teratailでの数式の記述の仕方がわかりませんでした。読みにくくてすいません)

特にわからないのはif文の条件式の部分ですが、
sum()とsliceのオーダーの求め方が合っているかわかりません。

このサイトを参考にするとsliceはO(k)だそうなので、
全体で見るとsliceの部分は、
\sum_{k=1}^{n}\sum_{l=1}^{k}l = \frac {1}{6}n(n+1)(n+2)
となるので、O(n^3)。

sum()も要素数でしょうか、
だとすると、上と同じ計算でO(n^3)。

よって、O(n^2) + 2O(n^3) = O(n^3)
とてもめちゃくちゃな計算になっている気がします・・。

よろしくお願いします。

Comments

[Do_you_1isten]

sliceの中身に詳しくないのですが、参考にしているサイトでばO(k+n)になっていますが、sliceのnは考慮しなくてもいい感じですか？

[退会済みユーザー]

すいません。よくわからないまま「Get Slice」の欄を見てO(k)にしたのですが、この場合だと「Set Slice」を見るのが適切なのでしょうか

Answer 1

ランダウ記号は、無限大まで大きくした場合にどのようなふるまいになるかを考えるものなので、

• 高次の項がある場合、それより次数の低い項は無視できる
• 定数項は無視できる

ようなものです。

O(3n^2+2n+1)=O(n^2)というようにできます。

（なお、teratailの入力に数式モードはなさそうです）

Comments

[退会済みユーザー]

ありがとうございます。
それは知っていたのですが、自分の計算方法が合っているのかどうかがわからないので、質問させていただきました。

Answer 2

count = 0
for i in range(n):
    for k in range(i+1,n+1):
        s_ = 0
        for j in range(i, k):
            s_ += s[j]
        if s == 0:
            count += 1

だと思うと三重ループになっていることがはっきりするのではないでしょうか。