시간복잡도

시간 복잡도 (Time Complexity)

입력에 크기에 대해서 시간이 얼마나 걸릴지 나타내는 방법.

# 1~n 까지의 합
sum = 0
for i in range(1,n+1):
    sum += i

위의 코드는 for문을 n번 돌기 때문에 시간 복잡도는 O(n) 이라고 나타낼 수 있다.

# 이중 for문
for i in range (1,n+1):
    for j in range(1,n+1):
        print(i,j)

위의 코드는 이중 for문으로, n번의 for문을 n번 돌아야 하므로 시간 복잡도는 O(n^2) 이다.

대표적인 시간 복잡도

• O(1) : 단순 계산
• O(logN) : N개를 절반으로 계속 나눔
• O(N) : for문
• O(NlogN)
• O(N^2) : 2중 for문
• O(N^3) : 3중 for문
• O(2^N) : 크기가 N인 집합의 부분 집합
• O(N!) : 크기가 N인 순열

시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 대략 1억이 1초정도라고 생각하면 된다.

시간복잡도의 계산

• 상수는 버림
  • O(2N^2) = O(N^2)
  • O(5) = O(1) -> 상수밖에 없을때는 1로 계산
• 두가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 버림
  • O(N^2 + N) = O(N^2)
• 두가지 항이 있을 때, 변수가 다르면 버리지 않음
  • O(N^2 + M)