파이썬 복잡한 계산

Question

나는 내가의 '빅 O'계산해야하는 다음과 같은 코드가 있습니다, 여기에 내가 올 것입니다 lst 가정

def f3(lst): 
    i = len(lst) 
    while i>0: 
     for j in range(i): 
      for k in range(j, 10**5): 
       print(i) 
     i -= 2 

길이가 n 목록, 그리고 작업이 O(1)을 ~ 두 번째 for은 매번 10 ** 5 번까지 반복되므로 상수이기 때문에 무시할 수 있습니다 (O(1)).

while은 n 번 실행되고 첫 번째 for 루프는 n/2 번 실행되므로 일반적으로 복잡도는 O(n^2)이어야합니다.

맞습니까? 내 친구가 O(n^4)라고 생각합니다.

감사합니다.

Answer 1

while 루프가 n/2 번 반복되었다고 올바르게 설정했습니다. 내부에 포함 된 외부 for 루프는 j = 1, 2, ... i에 대해 실행되며 i은 반복에서 len(lst), len(lst) - 2, ..., 1으로 설정됩니다. 따라서 j = 1, 2, ..., len(lst), j = 1, 2, ..., len(lst) - 2, ..., j = 1에 대해 바깥 쪽 for 루프가 실행됩니다. 합계로, 그것은 O(n^2) 루프의 바깥 쪽 for 반복입니다. 내부 for 루프는 일정한 횟수만큼 실행되지 않지만 최대 10**5 번 반복되며, 은입니다. 따라서 O(n^2)은이 함수의 런타임에 대한 올바른 상한값입니다.

---

다음은 약간 다른 설명입니다. 나는 다음과 같은 코드가 계산 시간의 측면에서 코드에 해당 동의 희망 :

def f3_simple(n): 
    i = n       
    condition = i>0    
    while condition:    
     r1 = range(i)    
     for j in r1:    
      r2 = range(j, 10**5) 
      for k in r2:   
       print(i)   
     i -= 2      
     condition = i>0   

여기 주석과 같은 코드입니다 :

def f3_simple(n): 
    i = n       # "length": O(1) 
    condition = i>0    # comparison: O(1) 
    while condition:    # executed O(n) times per function call 
     r1 = range(i)    # range(i): O(i) 
     for j in r1:    # executed O(n) times per WHILE iteration 
      r2 = range(j, 10**5)  # range(j, 10**5): O(10**5 - j) = O(1) 
      for k in r2:    # executed O(1) times per OUTER FOR iteration 
       print(i)    # print: O(1) 
     i -= 2      # decrement: O(1) 
     condition = i>0    # comparison: O(1) 

따라서, 총 런타임은 참으로 O(n^2)입니다.

Answer 2

대답이 O (n^3)이 아닙니까? 내부 루프는 조건을 검사하기 위해 런타임을 여전히 사용하고 있기 때문에 특정 위치 이후 j의 선형 함수이므로 O만큼 (n^3) n에 의해 j만큼 i의 합이 생성됩니까?