なぜ次のロジックのパフォーマンスがゼロですか？

Question

私はコーディネートのためにこの機能を書いており、性能は0、正しさは100％です。

A = [-1, -3] 
B = [1,2,3] 
C = [1,4,5,6,77,2] 

以下の関数は、最小整数を返しますが、存在しないintリストを返します。

def solution(A): 
    temp = 0; 
    tempLst = [] 
    for item in A: 
     temp = temp+1 
     if temp not in A: 
      tempLst.append(temp) 

    return min(tempLst) if tempLst else max(A) + 1 

なぜですか？私が望んでいたのは、ヒープ、itertools、部分的なことなしでそれを行うことでした。

Answer 1

あなたは効果的にネストされたループを持っています。

for item in A: 

この行は、Aのすべての要素をループします。

if temp not in A: 

...そしてあなたループ再びこれらの要素のそれぞれに対して、 Aの各要素に tempを比較します。

このコードの実行時間は、Aのサイズでは2次です。例えば。 Aに1000要素がある場合、このコードは1000 * 1000 = 1,000,000ステップで終了します。