Complexity

Time complexity

알고리즘의 연산량이 얼마나 걸리는지에 대한 척도를 나타낸다.

Complexity 계산 방법

• Complexity를 계산할 때는 input size(입력 크기)가 매우 큰 경우을 가정한다.
• 차수가 가장 큰 것만 중요하며 나머지 항들은 무시한다.
• Condfficient(계수)나 더해지는 상수는 무시한다.

Notation 종류

• Big-O natation: Upper bound(worst case)
  최악의 경우의 알고리즘 성능을 나타낸다. time complexity의 상한을 보장한다.
• Big-Ω notation: Lower bound(best case)
  최선의 경우의 알고리즘 성능을 나타낸다. time complexity의 하한을 보장한다.
• Big-θ notation: Tight bound(best&worst case)
  상한과 하한이 모두 동일한 경우를 나타내며, time complexity가 정확히 이 범위 안에 속한다는 것을 보장한다.

Big-O natation

Methematical expression for Big-O

• f(n): 알고리즘의 실제 시간 복잡도 함수
• g(n): 시간 복잡도의 Upper Bound를 표현하는 함수, 알고리즘의 성능이 아무리 나빠도 이 정도보다 나쁘지는 않다는 것을 보장한다.
• c: 양의 계수
• n0: 입력 크기가 충분히 크다는 가정의 특정 임계정
• n: 입력 크기 

알고리즘의 실제 성능 함수인 f(n)이 어떤 양수 c와 어떤 임계값 n0을 기준으로 c*g(n)보다 작거나 같아야 한다. 즉, n이 충분히 커지면 f(n)은 결국 c*g(n) 이하가 된다는 것이다.

Ex

 

대표적인 Big-O notation

Exponential time: O(2^n)

하나의 값을 구하기 위해 2의 n제곱 형태의 연산량이 필요하다.

int fibonacci(int n){
	if(n<=1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

Constant time: O(1)

어떤 input의 크기에도 한 번의 연산만 수행한다.

void constant_time(int arr[]) {
	printf("%d\n", arr[0]);
}

Logarithmic time: O(log n)

입력이 반, 반의 반, 반의 반의 반 형태로 줄어드는 연산이다.

void logarithmic_time(int n) {
	while (n > 1) {
		n /= 2;
	}
}

반복문이 입력 값을 절반씩 줄이며 수행하므로 로그 시간 복잡도이다.

Linear time: O(n)

모든 index를 순회하므로 선형 시간 복잡도를 가진다.

void linear_time(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}

Linearithmic time: O(n*log n)

데이터를 반으로 나누면서 각 단계에서 n번 연산을 수행한다.

void merge_sort_like(int n) {
	if (n <= 1) return;
	merge_sort_like(n / 2);
	merge_sort_like(n / 2);
}

Quadratic time: O(n^2)

이중 루프와 같이 두 바퀴를 도는 경우이다.

void quadratic_time(int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
		printf("(%d,%d) ", i, j);
		}
	}
}