시간 복잡도

시간 복잡도(Time Complexity)는 알고리즘의 실행 속도를 말한다

알고리즘은 하나의 문제를 풀 때 여러가지의 코드를 사용하여 풀 수 있다.
문제 풀이에 대한 방법은 여러가지가 있겠지만, 가장 실행 속도가 적은 최적의 코드를 짜는것이 효율적이므로 알고리즘을 짤 땐 이 시간 복잡도라는 것의 중요성이 높아진다.

이러한 시간 복잡도를 우리의 일상에 빗대어 좀 더 이해하기 쉽게 설명해보겠다.

약속을 앞두고 용인에서 수원까지 차를 타고 간다고 가정해보자.
이동시간은 총 1시간 30분이 걸렸다. 만약 구글에서 알려준 최단 경로로 갔더라면 1시간 내에 도착했을 것이다. 중요한 약속을 앞두기 전 30분 이라는 시간은 중요하므로 우리는 다음부터 시간을 효율적으로 사용해야겠다는 생각이 들 것이다.

컴퓨터 프로그래밍에서도 시간복잡도가 가장 낮은 알고리즘을 채택하여 이러한 상황을 개선하고 있다. 위의 예시처럼 용인에서 수원까지 택시를 타고 가는 절차를 알고리즘 이라고 하는데, 이때 수행하는 연산의 수를 시간 복잡도로 나타낸다. 위의 예시를 알고리즘으로 표현하면 아래와 같다.

function TakeCar(from, to){
  /*
  1. 차에 탑승한다
  2. 차 시동을 건다
  3. 용인에서 수원까지 운전한다
  4. 차 시동을 끈다
  5. 차에서 내린다
  */
}

위에서 가장 시간이 오래 걸리는 것은 무엇일까?

당연 3번이 가장 오래 걸릴것이다. 우리가 코드를 짜는 것은 모두 시간 복잡도를 계산할 수 있으므로 가장 오래걸리는 것, 위의 예시에서는 3번의 시간을 단축 시키는것이 시간 복잡도의 핵심이라고 말할 수 있게된다.




시간 복잡도는 보통의 경우 점근 표기법으로 사용되는데 주로 사용되는 점근 표기법은 아래와 같이 3가지가 있다.

• Big-O표기법 / O(N) : 빅오 표기법은 알고리즘 최악의 실행시간을 표기한다
• Ω 표기법 / Ω(N) : 오메가 표기법은 알고리즘 최상의 실행시간을 표기한다
• Θ 표기법 / Θ(N) : 세타 표기법은 알고리즘 평균 실행시간을 표기한다

위의 3가지 중에서 일반적으로 많이 사용되는 점근 표기법은 Big-O표기법으로 이것에 대해 조금 더 자세히 알아보자.

빅오 표기법

불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용되는 시간 복잡도 성능 표기법

빅오 표기법(Big-O)은 시간 복잡도를 나타내는 표기법 중 하나로 'O(입력)'으로 표기한다. 빅오 표기법의 성능 순서는 다음과 같이 나타낼 수 있다.

가장 왼쪽 O(1)으로 갈수록 실행 횟수가 적은 것 / 시간 복잡도가 낮은 것 이라 말할 수 있고, 가장 오른쪽 O(n!)으로 갈수록 실행 횟수가 많은 것 / 시간 복잡도가 높은 것 이라고 말할 수 있다.

O(1) 상수 시간
: 알고리즘이 입력에 관계 없이 연산이 수행된다. 즉 입력 데이터의 크기에 상관없이 일정한 시간이 걸린다.

function BigO(n){
  console.log("Hello Big-O");
}

O(n) 선형 시간
: 알고리즘이 입력한 개수인 n만큼 수행된다. 즉 입력 데이터가 증가할수록 처리시간도 증가한다.

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

O(n^2) 2차 시간
: 알고리즘이 입력한 개수의 n^2만큼 수행된다. 즉 입력 데이터가 증가할수록 처리시간이 제곱 배로 증가한다.

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