시간복잡도

알고리즘의 성능을 분석할때 

1. 입력을 넣었을때 정확한 출력이 나오는지

2. 얼마나 적은 메모리를 사용하고, 적은 시간이 걸리는지

여기에서 2번의 적은 시간에 관련된것이 시간복잡도 이다 

 

실제 실행 시간으로 알고리즘의 성능을 파악하는것은 문제가 있다

어떤 문제가 있냐

하드웨어나 사용언어에 따라 다른 실행시간이 나오기때문에 그게 알고리즘을 잘못 짜서 실행시간이 나온게 아니기때문에

 

그래서 시간복잡도를 쓰고

시간복잡도 표기법에는

빅오, 빅오메가 ,빅세타가있다.

빅오는 O(n)이런식으로 쓰고 n이 입력값이다

O(1)이렇게 상수가 들어가있으면 n이 얼마든지(입력값이 얼마나 커지든지) 항상 일정한 값이 나온다는것이다

O(n)

O(n logn)

O(n²)

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

linearTime(10);

위의 코드는 O(n)의 시간 복잡도를 가지고 있다.