質問: ``` 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)ですよね?
回答: ちゃんと動くコードを掲載してもらえれば、簡単な回答で済んだのですが、質問が変更されないのでめんどうな回答をします。 * これの計算量って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)を読んで勉強してください。