우리는 프로그램의 성능을 정확히 알 수 있는가?

고려할 것

• 입력 크기
• 하드웨어 성능
• 운영체제 성능
• 컴파일러 최적화
• 비동기 로직
• 그외 다수

프로그램의 성능을 정확히 파악하는 것은 불가능 합니다.

---

빅오 표기법 (시간복잡도)

시간복잡도를 나타내기 위한 방법 중 하나입니다.

위의 차트와 하단 순서만 기억해도 기본적으로 필요한 것을 갖췄다고 할 수 있습니다.

빅오 표현을 코드로

O(n) (선형시간)

선형시간은 입력받은 크기만큼 루프를 도는 것

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

}

O(log n) (지수시간)

로그시간은 입력받은 크기에 로그를 씌운 만큼 루프를 도는 것

for (let i = 1; i <= n; i*=2) {

}

O(n log n) (선형지수시간)

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

O(n^2) (2차시간)

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

1. n이 1024인 경우, 선형시간은 1024번 로그시간은 10번 루프를 도는 어마어마한 차이가 있습니다.
2. 이 위에 포함되지 않은 표기법은 알고리즘 문제 풀이시 사용되지 않습니다.

---

빅오 표기법은 점근법 표기법을 따름

계수 법칙

상수 k가 0보다 클 때 f(n) = O(g(n)) 이면 kf(n) = O(g(n)) 이다.
n이 무한에 가까울 수록 k의 크기는 의미가 없기 때문입니다.

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

}

for (let i = 0; i < n * 5; i+=1) {

}

합의 법칙

빅오는 더해질 수 있다.
f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) + g(n) = O(h(n)) + O(p(n))이다.

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

}

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

}

곱의 법칙

빅오는 곱해질 수 있다.
f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) g(n) = O(h(n)) O(p(n))이다.

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

다항 법칙

f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.

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

}

2가지만 기억하세요

1. 상수항은 무시

2. 가장 큰 항 외엔 무시

---

성능 측정 방법

Date 객체를 이용

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


const end = new Date().getTime();
console.log(end - start);

console.log("Start");
const start = new Date().getTime();
const N = 1000000000;

let total = 0;
for (let i = 0; i < N; i += 1) {
  total += i;
}

const end = new Date().getTime();
console.log(end - start);
console.log("Finish");

---

마무리

학부 생때 시간복잡도의 이론에 대해서 배우고 시험도 보고 했었는데

실제 개발, 프로그래밍에 어떻게 적용되는지는 전혀 모르는 상태였습니다.

하지만 이번에 각각의 선형시간, 로그시간, 선형로그시간, 2차시간 등의 시간복잡도가 반복문으로 구현되어 있는 코드들을 보면서 학습할 수 있어서 좋은 시간이였습니다

이번 시간을 통해 시간복잡도의 이론과 코드의 예시를 보았으니 계속 코딩 테스트, 알고리즘 공부를 하면서 코딩 테스트, 실제 개발에 활용할 수 있도록 하겠습니다.

---