코딩테스트 스터디 (시간복잡도)

GoGoDev·2022년 4월 6일
0

Coding-Test Study

목록 보기
2/8

프로그램 성능을 위해 고려해야할 것

  • 입력 데이터 크기
  • 하드웨어 성능
  • 소프트웨어 성능
  • 최적화
  • 비동기 로직
  • 등...

Big-O notation

시간 복잡도
빠름 -> 느린 순서

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

상수 시간 < 로그 시간 < 선형 시간 < 선형 로그 시간 < 이차 시간 < 지수 시간 < 팩토리얼 시간

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

입력 받은 n에 로그를 씌운 만큼 반복문을 돈다

O(nlogn)O(n log n)
for (let i = 0; i < n; i++){
	for (let j = 1; j <= n; j *= 2){
		...
	}
}
O(n2)O(n^2)
for (let i = 0; i < n; i++){
	for (let j = 1; j < n; j++){
		...
	}
}

1. 상수항은 무시

for (let i = 0; i < n * 3; i++){}

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

계수 법칙에 의해 계수는 무시되어 O(n + m)의 시간 복잡도를 가진다.

2. 가장 큰 항 외에는 무시

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

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

O(n^2 + n)의 시간 복잡도를 가지지만 작은 항은 무시되어 O(n^2)의 시간 복잡돌르 가진다.

성능 측정 방법

const start = new Date().getTime();

// 알고리즘 로직

const end = new Date().getTime();
console.log(end - start);
profile
🐣차근차근 무럭무럭🐣

0개의 댓글