コメントに書かせていただきましたが、ご質問中のコードは解釈の余地も何もなく明確にO(n^3)
なので、あなたが見つけなければいけないのは、明確にO(n^2)
のコード、と言うことになります。
(「sum
の呼び出し回数」と言うことなら質問のコードはO(n^2)
ですが、そんなものはアルゴリズムを議論する場合の計算量とは言いません。)
コメントの2個目のリンク中の質問側のコードを修正したものですが。これならO(n^2)
になります。
def solution(A):
start = None
end = None
max_total = 0
for i in range(len(A)):
tmp = 0
for j in range(i, len(A)):
tmp += A[j]
if max_total < tmp:
max_total = tmp
start = i
end = j
return max_total, start, end
A = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
ans = solution(A)
print(ans) #->(120, 0, 6)
肝心なところは、for j
で回している内側ループ内には、n
に応じて計算量が増えるような操作が入っていないことです。(計算量のことも考えずに「合計を求めるにはsum
を使わないとダサい」なんて短絡的な回答もあったようですが、ちゃんと1個ずつ足していかないと、for j
のループがO(n)
になりません。)
ネット上を探せばO(n * log n)
やO(n)
の回答が見つかります。既にお気づきだろうとは思いますが。
【ざっくりと時間計算量の見積もり方】
まず大前提は、アルゴリズムを議論するときのBig-Oは、特に断らない限り時間計算量を表していると言うことです。
つまり、
基準量n
の増減に対して、計算時間がどう増減するかを表す指標
であると言うことです。決して「見えている部分のループの回数」ではありません。
n
を増やしていったら処理時間がどんどん増えていくのに、見かけのループがないからO(1)
なんて指標を出されても困りますよね?
例えばこんな処理:
for i in range(len(A)):
A.sort()
#... ソート結果を使う単純な処理
があった場合に、for i
での一重ループだからO(n)
なんて結論を出したら、すぐにダメだしを食らうのはご理解いただけるでしょうか?
Pythonのsort
の平均時間計算量はO(n * log n)
ですから、それをn
回繰り返すならO(n^2 * log n)
と言うことになります。(もちろん#...
の部分の計算量はsort
の計算量に及ばない、と言うのが前提。)
と言うわけで、この回答のコードの時間計算量の見積もり。
時間コスト
--------
def solution(A):
start = None (この辺が全体コストに影響しないのは明白なんで無視)
end = None
max_total = 0
for i in range(len(A)): n^2 [=平均実行回数(n)*ループ1回分の実行コスト(n)]
tmp = 0 1
for j in range(i, len(A)): n [=平均実行回数(n/2)*ループ1回分の時間コスト(1)]
tmp += A[j] 1
if max_total < tmp: 1 (trueでもfalseでも時間計算量は定数)
max_total = tmp 1
start = i 1
end = j 1
return max_total, start, end
Big-O記法の特性として、「定数倍は無視」「低次の項は無視」なんてことがあるので、1+1
が1
になったり、n/2 * 1
がn
になったりしています。
ご質問のコードの時間計算量の見積もりはこんな感じです。
時間コスト
--------
def solution(A):
start = None
end = None
max_total = 0
for i in range(len(A)): n^3 [=平均実行回数(n)*ループ1回分の時間コスト(n^2)]
for j in range(i, len(A)): n^2 [=平均実行回数(n/2)*ループ1回分の時間コスト(n)]
tmp = sum(A[i:j+1]) n (`sum`関数の時間計算量は`O(n)`)
if max_total < tmp: 1 (trueでもfalseでもは同上)
max_total = tmp 1
start = i 1
end = j 1
return max_total, start, end
この中で意識しておられなかったのは、「sum
関数の時間計算量はO(n)
」の辺りでしょうか。計算量が仕様に記載してあることの多いsort
なんかに比べて「当たり前」の計算なんで、意識している人は少ないかも知れませんが、sum
関数の実行には足し合わせる要素数n
に比例した時間がかかります。
と言うわけで、
と言うことになります。
sum
みたいな組み込み関数の実行にどの程度時間がかかるものなのかも、時間計算量を議論する時には忘れてはいけません。
sum(A[i:j+1])
はO(n)
なんで、掲載のコードはO(n^3)
ですね。n
が増加した時に計算量が増える操作を「関数を呼んだ回数は1だから計算量コストも1」なんてやってると、アルゴリズムの一部を別関数にしただけで計算量が変わってしまうことになります。