[자료구조] 시간복잡도와 Big-O 표기법

시간복잡도와 Big-O 표기법

우리가 알고리즘 문제를 풀때 중요한 것은 해답을 찾는 것이다. 

더 나아가 그 문제를 좀더 효율적인 방법을 찾는 것도 굉장히 중요하다.

좀더 효율적인 방법을 고민해 본 적이 있다면 시간 복잡도를 고민한다는 것과 같은 말이다.

 

알고리즘에서 빠르다는 의미는 시간으로 표현하지 않는다. 알고리즘에서는 절차(step)의 수로 결정된다.

10번의 스텝이 필요한 알고리즘보단 5번의 스텝이 필요한 알고리즘이 더 훌륭하다고 볼수있다.

 

시간 복잡도를 표기하는 방법은 다음과 같다.

• Big-O(빅-오)
• Big-Ω(빅-오메가)
• Big-θ(빅-세타)

다른건 잘 모르겠고,Big-O 표기법이 자주 사용된다. 

빅오 표기법의 종류는 O(1), O(n), O(log n), O(n2), O(2n) 등이 있다.

 

O(1)

Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법이다.

O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않습니다.

다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.

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

let arr = [1, 2, 3, 4, 5,6,7,8,9,10,11,12,13,14]; // 이게 아무리 커도
let index = 1;
let result = O_1_algorithm(arr, index);	//우리는 [1]의 위치 값만 찾으면 끝
console.log(result); // 2

 

O(n)

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

예를 들어 입력값이 1일때 1초의 시간이 걸리고, 100이면 100초의 시간이 걸리는 알고리즘이라면, O(n)의 시간 복잡도를 가진 알고리즘이라 할 수 있다.

function O_n_algorithm(n) {
	let count=0
    for (let i = 0; i < n; i++) {	//n의 크기에 따라
		count++		      //카운트의 값이 바뀔거다.
	}
    return count;
}

function another_O_n_algorithm(n) {
  let count=0
	for (let i = 0; i < 2n; i++) {    //값이 커질수록 n의 앞쪽에 있는 수(계수)의 의미가 퇴색된다. 
	// do something for 1 second
    count++	
	}
     return count;
}

여기서 중요한 것은 n의 크기가 2배로 커지든 3배로 커지든 1000배로 커지든 모두 O(n)으로 표기가 된다. 

같은 비율로 증가하고 있다면 그것은 바로 O(n)의 시간 복잡도를 가진 알고리즘이다.

 

O(log n)

O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.

up & down 게임을 예로 들 수 있다.

 

한 단계, 즉 절차가 진행될때마다 경우의 수가 절반으로 줄어들기 때문에 단계를 진행할 수록 시간이 줄어든다.

 

O(n2)

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

예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면,

이 알고리즘의 시간 복잡도는 O(n2)라고 표현한다.

function O_quadratic_algorithm(n) {
let answer = [];
	for (let i = 1; i <= n; i++) {
		for (let j = 1; j <= n; j++) {
			answer.push(i+j);
		}
	}
    return answer;
}

let n =3;
let result =  O_quadratic_algorithm(n);
console.log(result) = [2,3,4,3,4,5,4,5,6];

 

O(2n)

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

우리가 알고있는 재귀로 구현하는 함수가 대표적인 예가 될 수 있다. (ex. 피보나치)

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

이건 시간이 엄청나게 걸릴 수도 있기 때문에 좀더 효율적인 방법을 찾는 것이 좋다.