関数呼び出しをするプログラムの時間計算量について

Question

前提・実現したいこと

配列が与えられた時に最長の１の数を返すプログラムを書いています。

#入力
A = [1,1,0,0,0,1,1,1,1,0,0]
#出力
4

発生している問題・エラーメッセージ

時間計算量（オーダ）を考えたいのですが、今回のプログラムだと最悪の場合で0(n^2)になるという理解で正しいでしょうか。
関数内で関数を呼び出す場合、今回のように繰り返し O(n)が更にn回繰り返されると考えられますか。

該当のソースコード

def loggestnum(A):
	max = 0
	for i in range(len(A)): #繰り返し O(n)
		p = countones(A, i) #繰り返し O(n)
		if (max<p):
			max = p
	return max

def countones(A,i):
	p = 0
	j = i
	while j <= len(A) and A[j] == 1:
		p = p+1
		j = j+1
	return p

A = [1,1,0,0,0,1,1,1,1,0,0]
print(loggestnum(A))

補足情報（FW/ツールのバージョンなど）

python 3.6

Answer 1

そのロジックの場合、1が続く回数をmとするとO(nm)って具合になるでしょう。mをnの線形関数とみなせればO(n^2)かもしれませんが、みなせないはず。分布に仮定を置いていいのなら（0と1が等確率でランダムに出現する、とか）平均計算量をnだけで表すことはたぶんできるでしょう。

関数呼び出しの有無は関係ありません。関数として書かないでループ内でベタに書いても計算量は同じです。

あと、連続する最大数を数えるだけならO(n)でやる方法があります。つまり、そのロジックはうまくないのです。

Comments

[退会済みユーザー]

ご回答いただきありがとうございます。O(nm)になるアルゴリズムとO(n^2)になるアルゴリズムのちがいがよく理解できていないのですが、 「O(n)が更にn回繰り返される」とき、2nになるかn^2になるのかはどのように区別すればいいのでしょうか。

O(n)に関しては、先ほど質問したのですが動的計画法のアプローチで書けば実現可能という理解で正しいでしょうか。 質問：https://teratail.com/questions/199121

[hayataka2049]

O(n)が更にn回繰り返されるなら紛れもなくO(n^2)ですが、リストの長さnと1が続く回数は別の変数ですから区別してO(nm)と書きます。

O(n)に関しては、動的計画法なんか使わなくてもできます。1が連続する回数を数えたら、その部分はすっ飛ばして続きから数え始めればいいだけなので。