[자료구조] 시간 복잡도

알고리즘 복잡도 표현 방법

1. 알고리즘 복잡도 계산이 필요한 이유

하나의 문제를 푸는 방법은 다양함 → 어느 방법이 더 좋은지 판단하기 위해서 복잡도가 필요함 → 가장 빨리 풀리는 알고리즘을 좋다고 판단할 수 있기 때문에 시간 복잡도가 가장 많이 사용됨

2. 알고리즘 복잡도 계산 항목

• 시간 복잡도: 알고리즘 실행 속도 → 가장 중요함
• 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

알고리즘 시간 복잡도의 주요 요소

• 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문
  → 반복문을 어떻게 구성했는지가 중요함

알고리즘 성능 표기법

• Big O 표기법: O(N)
  → 이 알고리즘이 최악의 경우에 시간이 얼마나 걸리는지 표기
  → 아무리 최악이라도 이정도의 성능은 보장! 이라는 뜻
• 오메가 표기법: Ω(N)
  → 알고리즘 최상의 실행 시간
• 세타 표기법: Θ(N)
  → 알고리즘 평균 실행 시간

Big O 표기법

• O(입력)
  → 입력 n에 따라 결정되는 함수
  → O(1),O(logn),O(n),O(nlogn),O(n^2),O(2^n),O(n!)등으로 표기
  → O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) 순으로 기하급수적으로 시간 복잡도가 증가함 (이때 logn의 베이스는 2임)
• n의 크기에 상관없이
  → 무조건 2회(상수회) 실행한다: O(1)
  → n에 따라 n번, n+10번, 3n+10번 등 실행한다: O(n)
  → n에 따라 n^2번, n^2+1000번 또는 100n^2-100번등 실행한다: O(n^2)

if n>10:
	print (n) 
#2번: O(1)

variable = 1
for index in range(n):
	printf(index)
#n+1번: O(n) 

variable = 1
for num in range(3):
	for index in range(n):
		printf(index)
#3n+1번 -> 상수에는 별로 관심없음: O(n)

variable = 1
for num in range(n):
	for index in range(n):
		printf(index)
#n^2+1번: O(n^2)

• Big O 입력값 표기 방법
  → 만약 시간 복잡도 함수가 2n^2+3n이라면
  → 가장 높은 차수만 챙김 : O(n^2)

예시: 1부터 n까지의 합을 구하는 알고리즘

1)

def sum_all(n):
	total = 0
	for i in range(1,n+1):
		total += i
	return total
#더하는 과정을 n번 반복: O(n)

2)

//n(n+1)/2 활용
def sum_all(n):
	return int(n*(n+1)/2)
#반복문 없이 한 줄의 계산식만 진행: O(1)

→ 이 경우, 후자의 알고리즘이 시간 복잡도 측면에서 더 좋은 알고리즘이라고 볼 수 있음