알고리즘_시간복잡도

Big-O 표기법의 종류💡

1. O(1)
O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
다시말해 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있다는 의미이다.

ex) 
function O1_Algorithm(arr,index){
return arr[index];
}

2. O(n)
O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율 로 증가하는 것을 의미한다.

ex) 입력값이 1일때 1초, 10일때는 10초, 100일때는 100초가 걸리는 알고리즘
function On_Algorithm(n){
	for(let i = 0; i<n; i++) {
	//do something for 1 sec
	}
}                        
function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

3. O(log n)
O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
자료구조의 BTS와 같은 로직도 O(log n)의 시간 복잡도를 가진 알고리즘이다.

4. O(n2)
O(n2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

ex) 이중반복문
function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}

5. O(2^n)
O(2^n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

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