시간 복잡도

시간 복잡도 유형

• 빅 오메가 : 최선일 때 (Best case)의 연산 횟수를 나타내는 표기법 : 1번
• 빅 세타 : 보통일 때 (Average case)의 연산 횟수를 나타내는 표기법 : N/2번
• 빅 오 : 최악일 때 (Worst case)의 연산 횟수를 나타내는 표기법 : N번

* N은 데이터의 갯수를 의미한다. 

---

시간 복잡도 예시

import random
findNumber = random.randrange(1, 101) # 1~100 사이의 랜덤 값 생성

for i in range(1, 101):
	if i == findNumber:
    	print(i)
        break

 

위 코드에서

- 랜덤 넘버가 1이라면 가장 빠른 시간 내에 넘버를 찾은 것이기 때문에 빅 오메가를 표기한다.

- 랜덤 넘버 1~100 사이의 숫자일 때 데이터 개수(N = 100)의 절반인 50이 평균적으로 나오기에 빅 세타 표기법을 표기한다. 

- 랜덤넘버가 100인 경우, 1~99까지 모든 과정을 거치고, 100이라는 숫자를 찾았기 때문에 빅 오로 표기한다.

---

코딩 테스트에서는 어떤 시간 복잡도 유형을 사용하는가?

- 빅 오 표기법으로 계산한다.

- 왜? 다양한 테스트 케이스에서도 시간복잡도가 최악일 때를 염두해서 합/불을 판단하기 때문이다.

---

시간 복잡도 실전 문제 예시

시간제한 2초로 조건을 만족해야 한다.

조건 : 4,000만 번 이하의 연산 횟수로 문제를 해결해야 한다.

 

파이썬 프로그램에서는 2,000만 번 ~ 1억 번의 연산을 1초의 수행 시간으로 예측한다. 

 

연산 횟수는 1초에 2,000만 번 연산하는 것을 기준으로 생각한다면 2초에 40,000,000(4,000만)이 된다.

 

연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출한다고 할 때

알고리즘 적합성 평가
버블 정렬 = (1,000,000)² = 1,000,000,000,000 > 40,000,000(4,000만) ⇢ 부적합 알고리즘
병합 정렬 = 1,000,000 log₂(1,000,000) = 약 20,000,000 < 40,000,000(4,000만) ⇢ 적합 알고리즘

 

* 버블 정렬은 O(N²)

* 병합 정렬은 O(nlogn)

---

시간 복잡도를 바탕으로 코드 로직을 개선할 수 있다?

가장 먼저 코드의 시간 복잡도를 도출해야 한다. 

시간 복잡도 도출 기준
1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

# 예제 1 : 연산 횟수 = N

N = 100000
cnt = 1

for i in range(N):
  print("연산 횟수" + str(cnt))
  cnt += 1

# 예제 2 : 연산 횟수 = 3N

N = 100000
cnt = 1

for i in range(N):
  print("연산 횟수" + str(cnt))
  cnt += 1

for i in range(N):
  print("연산 횟수" + str(cnt))
  cnt += 1

for i in range(N):
  print("연산 횟수" + str(cnt))
  cnt += 1

 

예제 1과 예재 2의 연산 횟수는 3배의 차이가 된다. 

 

N과 3N은 코딩테스트에서 같은 복잡도를 의미하기 때문에 상수는 복잡도 계산에서 제외한다. 

상수는 큰 변화를 주지 않는다.

# 예제 3 : 연산 횟수 = N²

N = 100000
cnt = 1

for i in range(N):
  for j in range(N):
    print("연산 횟수" + str(cnt))
    cnt += 1

 

이 코드는 N^2 이기 떄문에 큰 복잡도를 요구된다. 그래서 중첩을 확인해야 한다.

 

이와 같이 내가 작성한 코드의 시간 복잡도를 도출할 수 있다면 실제 코딩 테스트에서 시간 초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있고, 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할 수 있다.