시간복잡도(Time Complexity)

시간복잡도 : 알고리즘을 수행하는 데 필요한 시간을 추정하는 방법

• 알고리즘의 효율성을 평가하는 요소
• '빅 오 표기법'(Big O notation) : 최악의 경우의 실행 시간을 나타냄

---

---

O(1)

constant complexity
input 값에 관계없이 즉시 output 가능

public int O_1_algorithm(int[] arr, int index) {
  return arr[index];
}

int[] arr = new int[]{1,2,3,4,5};
int index = 1;
int results = O_1_algorithm(arr, index);
System.out.println(results); // 2

---

O(n)

linear complexity
입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것

public void another_O_n_algorithm(int n) {
	for(int i = 0; i < n * 2; i++) {
	// do something for 1 second
	}
}

• 입력값이 커질수록 계수의 의미는 퇴색되기에, 몇배가 되어도 O(n) 으로 표기

---

O(log n)

logarithmic complexity
Big-O표기법 중 O(1) 다음으로 빠른 시간 복잡도
경우의 수를 계속 절반으로 줄여나가며 정답을 찾는 BST(Binary Search Tree) 같은 경우

---

O(n^2)

quadratic complexity
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것

public void another_O_quadratic_algorithm(int n) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
				// do something for 1 second
			}
		for(int k = 0; k < n; k++) {
				// do something for 1 second
			}
		for(int l = 0; l < n; l++) {
				// do something for 1 second
			}
		}
	}
}

• 입력값이 커질수록 의미가 퇴색되기에 3n^2, 5n^2도 n^2으로 표현

---

O(2^n)

exponential complexity
가장 느린 시간 복잡도로 피보나치 수열이 대표적인 알고리즘
구현한 알고리즘의 시간 복잡도가 O(2^n)이라면 다른 접근 방식을 고민해 보는 것이 좋음

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

F(4)를 계산하기 위해 F(3)과 F(2)를 계산해야 하고, F(3)을 다시 계산하려면 F(2)와 F(1)을 계산해야함.