[자료구조] 빅오 표기법(Big-O nation)

빅오 표기법 (Big-O nation) 이란 
: 시간 복잡도를 나타내는 표기법
  입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변하는 지 설명하는 방법

시간복잡도
: 알고리즘을 수행하는데 연산들이 몇번 수행되는 가를 정량화 한 것을 나타낸다.

 

빅오 표기법 예제

 

1. O(1) : n의 값이 커질 수록, 아무 변화가 없고 실행 시간이 변하지 않는다.

 

function addUpTo(n) {
	return n * (n + 1) / 2;
}

 

2. O(n) : n이 커질수록 실행 시간이 1:1로 늘어남

 

function addUpTo(n) {
	let total = 0;
    for (let i = 1; i<=n; i++){
    	total += 1;
    }
    return total;
}

3.  O(n제곱) : n이 커질수록 실행 시간이 n제곱의 값으로 늘어남 (이중 for문)

 

function exponentiation(n) {
	for(let i =0; i<n; i++){
    	for(let j =0; j<n; j++){
        	console.log(i,j);
        }
    }
}

 

빅오 표기법을 적용하는 규칙

1. 상수를 이용해 계산할 때 , 덧셈, 뺄셈, 곱셈, 나눗셈을 포함

2. 루프가 있으면 복잡도가 루프의 길이 곱하기

     

 

 

---

 

reference : udemy JavaScript 알고리즘 & 자료구조 마스터 클래스