시간 복잡도

시간복잡도

입력된 자료의 양에 따라 알고리즘이 실행에 걸리는 시간을 말함.
시간복잡도의 표기법은 빅오(Big-O)를 쓴다.

시간복잡도의 예

1에서 N까지 합을 구하는 코드
아래쪽 코드의 실행 속도가 훨씬 빠름 => 시간복잡도가 낮음

# 시간 복잡도 O(N)
res = 0
N = int(input())

for i in range(1, N+1):
    res += i

print(res)

# 시간 복잡도 O(1)
N = int(input())
res = N * (N+1) // 2

print(res)

시간 복잡도 종류