시간 복잡도와 이중 for문

import time

list_a = range(3000)

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

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)

출력 결과는 0.31199999999807915 0.0이 나왔다.

 

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

 

list_a의 길이를 n이라 하자. (위 코드에서는 n=3000)

 

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

 

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

 

이 코드에선 n은 3000이므로 두 함수의 출력 시간은 3000배가 차이가 난다고 할 수 있겠다.

 

실제로 출력 결과를 보면 func0은 0.311초 동안 실행되었다고 하는데 func1은 0초로 너무 빨라서 실행 시간이 측정되지도 않았다. 0.000초도 안 걸린 것이다. 이 코드에서는 n이 3000이지만 실제로 이중 for문이 쓰이는 곳에서는 n값이 엄청 커질지도 모른다. 만약 이중 for문을 안 쓰고 func1처럼 for문 하나만 쓴다면 시간이 1/n으로 줄어들 것이다.

 

y=x와 y=x²의 차이는 어마어마하다..

 

n = 100
a = 0

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

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

아무튼 시간 복잡도 O(n²)은 피할 수 있으면 피하는 것이 좋다는 결론이다. (게다가 파이썬이라서 다른 언어보다 속도가 느리다..)

 

ref: https://coding-factory.tistory.com/608