루프의 시간 복잡도는 얼마입니까?

Question

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

시간 복잡도 란 무엇입니까? n/2 번 작동하지만 나머지는 어떨까요?

Answer 1

대답은 O(n^2)입니다.

첫 번째 루프는 ~ n, 두 번째 루프는 일정 시간, 세 번째 루프는 ~ n입니다.

Answer 2

여러분이 말했듯이, while 루프는 n/2 번을 반복하므로 O(n) 복잡합니다.

첫 번째 for 루프 (for j in range(i, i+10**8))는 상수 런타임이 O(1)입니다.

두 번째 for 루프의 복잡도는 O(n)이며 n+n^2 회를 실행합니다.

이

코드를