알고리즘의 시작복잡도

• 알고리즘의 시간복잡도
• 시간복잡도의 Big-O 표기법
• Big-O 표기법의 4가지 법칙

알고리즘의 시간복잡도

효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구현하는 것이다.

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

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

• 빅오 표기법의 순서 (커질수록 시간복잡도가 높아짐)

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

각 표기법의 예시

• O(1)

for (let i = 0; i < 1; i+= 1){
	// ...
}

• O(n)

for (let i = 0; i < n; i+= 1){
	// ...
}

• O(log n)

for (let i = 0; i < n; i*= 2){
	// ...
}

• O(n log n)

for (let i = 0; i < n; i+= 1){
	for (let i = 0; i < n; i*= 2){
	// ...
	}
}

• O(n^2)

for (let i = 0; i < n; i+= 1){
	for (let i = 0; i < n; i+= 2){
	// ...
	}
}

Big-O 표기법의 4가지 법칙

• 계수 법칙

// O(n)
for(let i = 0; i < n; i += 1){
	// ...
}
// O(n)
for(let i = 0; i < n * 5; i += 1){
	// ...
}

• 합의 법칙

//  O(n + m)
// 계수 법칙에 의해 5는 사라진다.
for(let i = 0; i < n; i += 1){
	// ...
}

for(let i = 0; i < m * 5; i += 1){
	// ...
}

• 곱의 법칙

// O(n^2)
// 계수 법칙에 의해 5는 사라진다.
for(let i = 0; i < n; i += 1){
	for(let i = 0; i < n * 5; i += 1){
		// ...
	}
}

• 다항 법칙

// O(n^3)
for (let i = 0; i < n * n * n; i+= 1){
	// ...
}