시간 복잡도

• 알고리즘 선택의 기준이 됨
• 파이썬 프로그램에서는 2,000만번~1억 번의 연산을 1초의 수행시간으로 예측

시간 복잡도 표기법

• 빅-오메가
  최선일 때(best case)의 연산 횟수를 나타낸 표기법

• 빅-세타
  보통일 때(average case)의 연산 횟수를 나타낸 표기법

• 빅-오
  최악일때(worst case)의 연산 횟수를 나타낸 표기법

  시간복잡도 예제 코드

  import random
  findNumber = random.randragne(1, 101)
  
  for i in range(1, 101):
  	if i == findNumber:
     	print(i)
  			break

  빅-오메가 표기법의 시간 복잡도는 1번
  빅-세타 표기법의 시간 복잡도는 50번
  빅-오 표기법의 시간 복잡도는 100번

코딩 테스트에서의 시간 복잡도

• 코딩 테스트의 합격/불합격 판정은 모든 케이스를 통과해야만 하므로, 빅-오케이스를 선택해야함.
  

시간 복잡도 활용

수 정렬하기(백준 2750)

버블 정렬의 시간 복잡도 : O(n^2)
병합 정렬의 시간 복잡도: O(nlogn)

• 시간 제한이 1초 이므로 2,000만번 이하의 연산 횟수로 문제를 해결 해야 함

연산 횟수 계산 방법

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

• 위 문제의 경우 n의 최댓값이 1,000
  - 버블 정렬(n^2) = (1,000)^2 = 1,000,000
  - 병합 정렬(nlogn) = 1,000log1,000 = 약 1,000
  ->병합 정렬이 더 적합

시간 복잡도를 바탕으로 코드 로직 개선

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

예1:연산 횟수 N

n = 100,000
cnt = 1

for i in range(n):
	cnt += 1

예2:연산 횟수 3N

n = 100,000
cnt = 1

for i in range(n):
	cnt += 1
    
for i in range(n):
cnt += 1
    
for i in range(n):
cnt += 1

연산 횟수가 3배 차이나는 것 같지만 둘 다 O(n)의 시간 복잡도를 가짐

예3:연산 횟수 N^2

n = 100000
cnt = 1

for i in range(n):
	for j in range(n):
    	cnt += 1

위 코드의 시간 복잡도는 O(n^2)