시간 복잡도와 이중 for문

import time

# 0, 1, ..., 9998, 9999
list_a = range(10000)

# list_a의 누적합을 구한다. 시간복잡도는 Θ(n²)
def func0(list_a):
    ret = []
    for i in range(len(list_a)):
        suma = 0
        for a in list_a[:i+1]:
            suma += a
        ret.append(suma)
    return ret

# list_a의 누적합을 구한다. 시간복잡도는 Θ(n)
def func1(list_a):
    ret = []
    suma = 0
    for a in list_a:
        suma += a
        ret.append(suma)
    return ret

start0 = time.monotonic()
ret0 = func0(list_a)
elapsedtime0 = time.monotonic() - start0

start1 = time.monotonic()
ret1 = func1(list_a)
elapsedtime1 = time.monotonic() - start1

# 두 함숫값이 같다면
if ret0 == ret1:
    print(elapsedtime0, elapsedtime1)

위 코드를 실행해보면 func0의 실행 시간은 2.1089999999999236초, func1의 실행 시간은 0.016000000000076398초임을 알 수 있다.

두 함수의 반환값은 같지만 실행 시간은 다르다. 왜 그럴까?

list_a의 길이를 n이라 하자. 위 코드에서는 n=10000이다.

func0을 보면 이중 for문이 사용되었다. 바깥 for문은 list_a의 길이, 즉 n번 반복되고, 안쪽 for문은 i번 반복되는 것을 알 수 있다. 바깥 for문이 한 번 돌 때마다 i는 1씩 증가한다. 여기서 i는 첫째항이 0, 마지막항이 n-1, 공차가 1인 등차수열의 원소이다. 따라서 안쪽 for문이 반복되는 횟수는 등차수열의 합 공식에 의해 n(n-1)/2이다. 연산 횟수가 n에 대한 이차식으로 나타내어진다. 시간 복잡도는 연산 횟수에 비례하므로 시간 복잡도를 Θ(n(n-1)/2) = Θ(n²) 이라고 할 수 있다.

func1을 보면 for문이 하나이다. 반복문이 n번만큼 반복되므로 시간 복잡도는 Θ(n)이다.

이미지 출처: Comparison computational complexity - Time complexity - Wikipedia  

Time complexity - Wikipedia

N=n과 N=n²의 차이는 어마어마하다.

n = 100
a = 0

for x in range(10):
    for y in range(n):
        for z in range(n-10):
            a += 1

위 코드는 삼중 for문이지만 시간 복잡도는 여전히 Θ(n²)이다.
왜냐하면 명령 횟수가 (n-10)*n*10 으로 n에 대한 이차식으로 나타내어지기 때문이다.