for文の計算量について

Question

cnt=0
for i in range(n):
 for j in range(i,n):
  sum=0
  for k in range(i,j):
   sum+=a[k]
  if sum==N:
   cnt+=1
retun cnt

これの計算量ってO(n^3)ですよね？

Comments

[ppaul]

SyntaxError: invalid syntax
の出るコードの計算量はゼロです。

Answer 1

ちゃんと動くコードを掲載してもらえれば、簡単な回答で済んだのですが、質問が変更されないのでめんどうな回答をします。

• これの計算量ってO(n^3)ですよね？

分かりません。
O(n^2)でないことは断言できますが、適当に補ってO(n^4)とかO(n^5)となるようなコードを作ることは可能です。

同じ程度に不完全なC言語で書かれたコードで同じような質問をされたとすれば、O(n^3)であることは断言できます。
Pythonには特殊メソッドというものがありますので、aのクラス次第で、O(n^4)でもO(n^5)でも作れてしまいます。
最近のC++は詳しくはありませんが、aの宣言が書かれていなければ同じ事がいえると思います。
FORTRNは古い規格の言語ですが、PythonやC++とは別の理由によってO(n^4)でもO(n^5)でも作れてしまいます。

初心者の方には難しいかもしれませんが、Pythonについての詳しいことを知りたければ、object.getitem(self, key)を読んで勉強してください。

Answer 2

ifを無視しまして最悪計算量で考えますとO(n^3)でございます。

Comments

[quickquip]

ifが停止条件になっていないので無視して大丈夫かと。

[m2l]

SyntaxError: invalid syntax
と仰っている方がおりまして、それを無視する形でお答えしますという意味合いですね。