[알고리즘] 시간복잡도

코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

시간복잡도

• 시간복잡도란 입력크기와 문제를 해결하는데 걸리는 시간(프로그램의 연산횟수 : 연산량)과의 함수관계를 의미합니다.
  예) T(n) = 2n² + 3n

---

시간복잡도를 표현하는 방법

1. Big-O 표기법 : 최악의 상황으로 연산량을 계산하는 표기법

• 배열에서 5를 찾는 경우(순차탐색)

2. Big-Ω 표기법 : 최선의 상황으로 연산량을 계산하는 표기법

• 배열에서 5를 찾는 경우(순차탐색)

3. Big-θ 표기법 :최악과 최선의 평균으로 연산량을 계산하는 표기법

---

Big-O 표기법의 종류

시간복잡도는 대부분 Big-O 표기법으로 사용하므로 Big-O 표기법의 종류에 대해서 알아보겠다.

1. O(1) : 처리해야할 데이터양(입력크기)와 상관없이 항상 일정한 연산량을 갖고 있는 알고리즘

for i in range(10): 
	sum += i

2. O(n) : 처리해야할 데이터양과 비례해 연산량도 증가하는 알고리즘

for i in range(n):
	sum = sum + i

• T(n) = 2n
• Big-O 표기법은 계수를 생략하므로 O(n)

3. O(n²) : 처리해야할 데이터양이 증가할수록 데이터양의 제곱만큼 연산량이 증가하는 알고리즘

for i in range(n): 
	sum = 0;
	for j in range(n): 
    	sum = sum + i

• T(n) = 2n² + n
• Big-O 표기법은 최고차항만 표기하므로 O(n²)

for i in range(n): 
	sum = 0;
	for j in range(i+1): 
    	sum = sum + i

• T(n) = ½n² + ½n
• Big-O 표기법은 최고차항만 표기하므로 O(n²)

4. O(㏒n) : 처리해야할 데이터양이 증가해도 연산량이 별로 증가하지 않는 알고리즘

n = 1024
cnt = 0
i=1
while i < n:
	i=i*2
	cnt += 1 
print(cnt)

5. O(n㏒n)

n = 1024
cnt = 0
for i in range(n):
	j=1
	while j < n:
		j=j*2
		cnt += 1
print(cnt)

---

위와 같이 시간복잡도를 학습한 후 풀이한 문제는 아래와 같다.

• 두 수의 합