시간 복잡도

시간복잡도

빅오 표기법 Big-O notation

• 프로그램의 성능을 알기 위해 고려해야 하는 것들 : 입력으로 들어오는 데이터의 크기, 프로그램이 동작하는 하드웨어 성능, 프로그램을 실행 관리하는 운영체제 성능, 프로그램을 build하는 컴파일러 최적화, 프로그램이 thread 혹은 process 사용시 비동기 로직 고려
• 프로그램의 성능을 정확하게 파악하는 것은 불가능하므로 컴퓨터 과학자들은 대략적인 성능을 비교하기 위한 상대적인 표기법을 사용하기로 했다. 그것이 바로 빅오 표기법이다.
• 시간복잡도를 나타내기 위한 방법 중 하나
• 빅오 표기법의 상대적인 성능을 비교
  • O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
  • 상수시간<로그 시간<선형시간<선형로그시간<2차시간<지수시간<팩토리얼시간 라 불리기도 한다. 참고로 여기서의 log의 밑은 2이다.
  • 빅오에 쓰인 n이 전부 같은 값이라고 가정할 때 O(1)이 가장 빠르고 위 순서대로 점점 느려진다.
• 지수시간이나 팩토리얼 시간 같은 경우 특정한 상황이 아니라면 가급적 사용하면 안된다.
• 코딩테스트에는 n^3이상 시간복잡도가 소요되는 경우는 거의 없다.
• 식에 계수나 상수 연산이 없는 이유 : 빅오표기법은 점근적 표기법을 따르기 때문이다.(점근적 표기법은 함수의 증감 추세를 비교하는 방법이다.)

선형시간

• 입력한 크기 만큼 loop를 도는 것
• 선형시간과 로그시간에는 어마어마한 차이가 존재: 예를 들어 n이 1024인 경우 선형시간은 1024번 루프를 돌지만 로그시간은 단 10번만 루프를 돌면 된다.
• O(n)

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

로그시간

• O(log n)

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

  • 입력받은 n에 log를 씌운 만큼만 loop를 돌게 됨

선형 로그 시간

• O(n log n)

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

선형지수 시간(2차 시간)

• 선형지수시간은 단순히 선형시간에 지수시간을 곱한 시간
• 2차 시간은 n의 제곱만큼만 루프를 돈다.
• O(n^2)

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

빅오 표기법의 4가지 법칙

• 표기할 때 딱 두가지만 기억하면 된다.
  • 1. 상수항은 무시

       // 계수 법칙에 의해 계수는 무시된다
       // 그리하여 O(n+m)으로 표기된다.
       for(let i = 0; i < n * 6; i += 1) {
       }
       for(let i = 0; i < m * 3; i += 1) {
       }

  • 2. 가장 큰 항 외엔 전부 제거(무시)

       // O(n^2 +n)이지만 작은항은 무시하여 O(n^2)으로만 표기해도 된다.
       for(let i = 0; i < n; i += 1) {
       }
       for(let i = 0; i < m * 3; i += 1) {
        for(let j = 0; j < n; j += 1) {
        }
       }

1. 계수 법칙

• 상수 k가 0보다 클 때 f(n) = O(g(n))이면 kf(n) = O(g(n))이다. n이 무한에 가까울 수록 상수 k의 크기는 의미가 없기 때문에 상수 k는 생략해서 표현한다. 하지만 상수 k가 클수록 실제 성능에는 영향을 미칠 수 있다.
• 예시

  // 두 루프는 같은 O(n)으로 표기된다.
  for(let i = 0; i < n; i += 1) {
  }
  for(let i = 0; i < n * 5; i += 1) {
  }

2. 합의 법칙

• f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) + g(n) = O(h(n)) + O(p(n))이다. 빅오끼리 더할 수 있다.
• 예시

  // 두 루프를 합쳐 O(n + m)으로 표기할 수 있다.
  // 계수 법칙에 의해 5는 사라진다.
  for(let i = 0; i < n; i += 1) {
  }
  for(let i = 0; i < m * 5; i += 1) {
  }

  3. 곱의 법칙

• f(n) = O(h(n))이고 (n) = O(p(n))이면 f(n) * g(n) = O(h(n)) * O(p(n)) 이다. 빅오끼리는 곱해질 수 있다.
• 2차 시간이나 선형로그 시간 같은 시간복잡도는 곱의 법칙을 통해 나온 것이다.
• 예시

  // 두 루프를 합쳐 O(n^2)으로 표기할 수 있다.
  // 계수 법칙에 의해 5는 사라진다.
  for(let i = 0; i < n; i += 1) {
    for(let j = 0; j < n * 5; j += 1) {
    }
  }

  4. 다항 법칙

• 다항식일 때 표현하는 방법
• f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.
• 예시

  // 다음 루프는 O(n^3)으로 표기할 수 있다.
  for(let i = 0; i < n * n * n; i += 1) {
  }

---

js에서 성능 측정 방법

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”)
  
  // output
  //Start
  // 1114 //초로 환산하면 약 1.1초 정도
  // Finish