(끼에엑 Big-O 표기법이다!)

1년도 더 전에 썼던 글이지만 (분명 참고 자료가 있었을텐데 기억나지 않음)
가끔 한 번씩 리마인딩 하기 좋을 것 같아서 남겨놓은 자료.
그땐 cpp로 코드예시를 들었지만, 이번엔 go로 바꿔보았다.

알고리즘의 분석

알고리즘의 자원 사용량을 분석한다.
주로 자원은 통상적으로 실행 시간, 메모리, 저장장치, 통신 등을 뜻하나
여기선 실행 시간의 분석에 대해서 다룬다.

시간 복잡도

• 실행 시간은 실행 환경에 따라 달라진다.
  • 하드웨어, 운영체제, 언어, 컴파일러 등
• 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트한다.
• 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현한다.
• 데이터의 크기가 같더라도 실제 데이터에 따라서 달라진다.
  • 최악 시간 복잡도 (worst-case analysis)
  • 평균 시간 복잡도 (average-case analysis)

점근적 분석

• 점근적 표기법을 사용
  • 데이터의 개수가 n→∞일 때, 수행 시간이 증가하는 증가율로 시간 복잡도를 표현하는 기법이다.
  • Θ-표기, O-표기, Ω-표기 등이 있다

상수 시간복잡도

입력으로 n개의 데이터가 저장된 배열이 주어지고, 그 중 n/2번째 데이터를 반환하는 경우

func find(data []int, n int) int{
	return data[n/2];
}

→ n에 관계없이 상수 시간이 소요되며, 알고리즘의 시간 복잡도는 O(1)이다.

선형 시간복잡도

n개의 데이터가 저장된 배열이 주어지고, 그 합을 구하여 반환하는 경우

func sum(data []int, n int) int{
	res = 0;
	for int i=0;i<n;i++ {
		res += data[i]; // 가장 자주 실행되는 문장
	return res;
}

→ 실행 횟수는 항상 n번이다.
→ 이처럼 가장 자주 실행되는 문장의 실행 횟수가 n번이라면, 모든 문장의 실행 횟수의 합은 n에 선형적으로 비례하고, 모든 연산들의 실행 횟수의 합도 n에 선형적으로 비례한다.
→ 선형 시간 복잡도를 가지며, 알고리즘의 시간 복잡도는 O(n)이다.

선형 시간복잡도 : 순차탐색

배열이 주어지고, 배열 안에 정수 target이 있는지 검색하는 경우

func find(data []int, n, target int){
	for int i=0;i<n;i++ {
		if data[i] == target // 가장 자주 실행되는 문장
			return i;
		}
	return -1;
}

→ worst-case analysis는 n 이다.

배열에 중복된 원소가 있는지 검사하는 경우

func isDistinct(n int, data []int) bool{
	for int i=0;i<n-1;i++ {
		for int j=i+1;j<n;j++ {
			if(data[i] == data[j]) // 가장 자주 실행되는 문장
				return false;
			}
		}
	}
	return true;
}

→ worst-case analysis는 n(n-1)/2 이다.
→ 시간복잡도는 O(n^2)로 나타낸다.

Q. 증가율이 곱셈일 경우?

for int i=1;i<n;i*=2 {
	// 가장 자주 실행되는 문장
}

→ worst-case analysis는 O(log2(n))

점근적 표기법

• 알고리즘에 포함된 연산들의 실행 횟수를 표기하는 하나의 기법
• 최고 차항의 차수 만으로 표시
• 가장 자주 실행되는 연산 혹은 문장의 실행 횟수를 고려하는 것으로 충분함.

O-표기법 (빅오)

• upper bound를 표현

Ω-표기법(오메가)

• lower bound를 표현
• 차수가 k≥0인 모든 다항식은 O(n^k)이다.

Θ-표기법(세타)

• upper bound와 lower bound를 동시에 표현