시간복잡도

• 빅-오메가 : 최선일 때
• 빅-세타 : 보통일 때
• 📍 빅-오 O(n) : 최악일 때

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

for i in range(1, 101):
	if i == findNumber:
    	print(i)
        break
# 빅-오메가 : 시간복잡도 1번
# 빅-세타 : 시간복잡도 N/2번 = 50번
# 빅-오 : 시간복잡도 N번 = 100번

코딩테스트에서는 빅-오 표기법(O(n)) 기준으로 수행 시간 계산하는 것이 좋다.

빅-오 표기법 O(n)

수 정렬하기 예제

• 데이터의 크기와 시간 제한 항상 고려!
• 1 <= N <= 1,000,000
• 최악의 케이스를 고려해야 하기 때문에
  - 데이터 크기(N)는 1,000,000값
  - 시간 제한은 1초에 2,000만번이므로, 2초에 40,000,000 번 이하의 연산 횟수로 문제 해야해야 함
• 즉, 연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출
• 코딩테스트에서는 약 2,000만 번 ~ 1억 번의 연산이 대략 1초 정도 걸리나 최악의 케이스로 2,000만 번으로 기준!

시간복잡도 예제

• 버블 정렬 시간복잡도 공식 = O(N제곱)
  = 1,000,000 * 1,000,000 = 1,000,000,000,000 > 40,000,000 => 부적합 알고리즘
• 병합 정렬 시간복잡도 공식 = O(nlogn)
  = 1,000,000 * log2(1,000,000) = 약 20,000,000 < 40,000,000 => 적합 알고리즘
  ** log2(1,000,000) = 20

연산 횟수는 1초에 2,000만 번 기준
시간 복잡도는 항상 최악, 즉 데이터의 크기가 가장 클 때를 기준

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에 제외한다.

• 연산 횟수 = N

N = 100000
cnt = 1

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

• 연산 횟수 = 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

위 두 코드는 같은 시간복잡도를 갖는다.
3N의 상수인 3을 무시하는 O(n)으로 같다.

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

• 연산 횟수 = N2(제곱)

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