루프의 시간 복잡도

Question

다음은 제 코드입니다. 이 코드는 시간 복잡성을 찾아야합니다. 나는이 코드에 대해 두 가지 답을했다. 하나는 O (n log (n))이고 O (n)입니다. 그러나 둘 다 틀리다. [루프 구조를 기반으로 이러한 대답을했습니다. while 루프 내에서 for 루프를 사용하여 일부 코드를 보았습니다. 이러한 유형의 코드는 O (n log (n))의 시간 복잡도를 갖습니다.] 어느 누구도 나에게 올바른 대답을 제안 할 수 있습니까?

def sort1(lst): 
    swapFlag = True 
    iteration = 0 
    while swapFlag: 
     swapFlag = False 
     for i in range(len(lst)-1): 
      if lst[i] > lst[i+1]: 
       temp = lst[i+1] 
       lst[i+1] = lst[i] 
       lst[i] = temp 
       swapFlag = True 

     L = lst[:] # the next 3 questions below refer to this line 
     iteration += 1 
    return lst 

Answer 1

그것은 O(n^2)의 시간 복잡도를 가지고 bubble-sort의 일종처럼 보인다.
내부 for 루프를 반복 할 때마다 최대 요소가 목록의 끝으로 이동하므로 n-1 개의 비교가됩니다. 목록에 n 개의 요소가 있고 내부의 for 루프는 각 요소 당 한 번 실행되어 O(n^2)이됩니다.