Pythonの - 時間計算量O（N ** 2）

Question

次のコードでは、我々はOを得る（N ** 2）ここで、誰も私を伝えることができます：

def solution(X, A): 
    assistant = list(range(1, X+1)) 
    assistant_sum = sum(assistant) 
    helper = set() 
    if X not in A: 
     return -1 
    if A.count(A[0]) == len(A): 
     if A[0] == 1: 
      return 0 
     return -1 
    for y in A: 
     helper.add(y) 
    sorted_helper = sorted(list(helper)) 
    if sum(sorted_helper[0:X]) == assistant_sum: 
     helper = set() 
    for index, i in enumerate(A): 
     try: 
      helper.add(i) 
      if len(list(helper)[0:X]) == len(assistant) and int((list(helper)[0]+list(helper)[X-1])/2.0*len(helper)) == assistant_sum: 
       return index 
     except IndexError: 
      pass 
    else: 
     return -1 

はオンライン時間複雑性をチェックする方法はあります？ 助けてくれてありがとう！

Answer 1

helperは、あなたのループfor index, i in enumerate(A)のためにあなたがしてlist(helper)、というNの長さでlist(helper)

を呼び出しているではAと同じ長さまで可能セットですfor index, i in enumerate(A)がO(N)で、O(N)です。

O(N)のループ内O(N)の文はO(N**2)