Pythonコードの時間の複雑さを理解する

Question

私は時間の複雑さの問題に全く新しいです。私は、Codilityの演習のためのPythonコードを書いています。私が書いたコードは、O（N * N）の時間複雑さを伴うタイムアウトエラーを返します。予想される時間の複雑さはO（N）です。整数Aのリストを考えると

、 私はA[0:i]の合計と、すべてのインデックスAでiためA[i:]の合計との間の最小差を計算しようとしています。

はここに私のソリューションです：

def solution(A): 
# write your code in Python 2.7 
a=[] 
for i in range(1,len(A)): 
     a.append(abs(sum(A[0:i])-sum(A[i:len(A)+1]))) 
return min(a) 
pass 

私はまだ同じ複雑さを取得するには、次

import sys 
def solution(A): 
# write your code in Python 2.7 
    a=sys.maxint 
    for i in range(1,len(A)): 
     temp=abs(sum(A[0:i])-sum(A[i:len(A)+1])) 
     if temp<a: 
      a=temp 
    return a 
    pass 

を実装することで、コードを改善しようとしました。私はabsステップが計算に多くの時間を費やしていることを理解しています。このコードの時間の複雑さをどのように減らすのですか？時間の複雑さの問題を直観的に見る方法はありますか？ループの各反復で

Answer 1

、 索引i、 とインデックスi後の要素の和までの要素の合計を再計算します。 これは効率的ではありません。 あなたが行くにつれて合計を累積することができるためです。

• 違いのリストを作成する必要はありません：

  suffix = sum(A) 
  prefix = 0 
  mindiff = suffix 
  
  for a in A: 
      prefix += a 
      suffix -= a 
      mindiff = min(mindiff, abs(prefix - suffix)) 
  
  return mindiff 
  

  他あまりにもあなたのコードに問題がありました。

• A[i:len(A)+1]の終了インデックスがAの範囲を超えているため、読むのが紛らわしく、Pythonでリストのインデックス付けが混乱する可能性があることを示唆しています。これはA[i:len(A)]、またはそれ以上のものであったはずです。単純にA[i:]です。

時間の複雑さの問題を見ているの直感的な方法はありますか？

絶対に。 ここでの直感は、ある範囲の値の合計を計算するには、 を反復処理する必要があります。 だから、そこにはO(N)です。 これが別のO(N)ループ内にある場合は、 となり、全体の複雑さはO(N*N)になります。 あなたの過ちは合計のコストを見落としていました。