Big-O 표기법

• 알고리즘의 성능을 수학적으로 표현해주는 표기법
• 실제 러닝타임이 아닌 단위시간에 따른 알고리즘의 성능 예측
• 횟수가 극한으로 수렴할 때를 상정하기 때문에 상수는 무시한다.

O(1)

void function(int[] n) {
	System.out.println(n[0]);
}

해당 메소드는 배열 n의 크기와 상관없이 단 한번의 결과를 반환한다.
이 알고리즘의 시간 복잡도는 O(1)이다.

O(n)

void function(int[] n){
	for(int i : n) {
    	System.out.println(n[i]);
    }
}

해당 메소드는 배열 n의 크기만큼 반환 횟수가 늘어난다.
이 알고리즘의 시간 복잡도는 O(n)이다.

O(n^2)

void function(int[] n) {
	for(int i : n) {
		for(int j : n) {
			System.out.println(n[i] + n[j]);
		}
	}
}

해당 메소드는 배열 n의 크기가 늘어날때마다 반환 횟수가 거듭해서 늘어난다.
이 알고리즘의 시간 복잡도는 O(n^2)이다.

O(nm)

void function(int[] n, int[] m) {
	for(int i : n) {
		for(int j : m) {
			System.out.println(n[i] + m[j]);
		}
	}
}

해당 메소드는 배열 n과 m의 크기의 곱 만큼의 반환 횟수가 나오게 된다.
이 알고리즘의 시간 복잡도는 O(nm)이다.
n과 m의 크기가 같다면 O(n^2)와 같은 시간 복잡도를 가진다.

O(n^3)

void function(int[] n) {
	for(int i : n) {
		for(int j : n) {
			for(int k : n){
				System.out.println(n[i] + n[j] + n[k]);
			}
		}
	}
}

해당 메소드는 배열 n의 크기가 늘어나는 크기의 세제곱만큼 반환 횟수가 늘어난다.
이 알고리즘의 시간 복잡도는 O(n^3)이다.

O(log n)

void binarySearch(int key, int n[], int low, int high) {
	int mid;

	while(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) {
			System.out.println(mid);
		} else if(key < arr[mid]) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	return -1; // 탐색 실패 
}

해당 메소드는 배열에서 특정 숫자의 위치를 찾는 방법 중 이진탐색(=이분탐색, binary search)이다. 이진탐색의 횟수는 배열 n의 길이가 1이 될때까지 2로 나눠지는 횟수와 동일하다. 횟수를 K라고 하고 이를 수식화 하면 log_2(n) = k가 되고, 이를 시간복잡도로 나타낸 것이 O(log n)이다.

---

위에서 익힌 특정 시간복잡도들은 표를 통해 쉽게 비교해볼 수 있다. O(1)가 가장 빠를 확률이 높고, O(n!)가 가장 느릴 확률이 높은것을 확인할 수 있을 것이다.

참고 문서
엔지니어대한민국 - [자료구조 알고리즘] 빅오(Big-O)표기법 완전정복