1. 시간복잡도

시간복잡도

시간 복잡도란 특정한 크기의 입력에 대해 알고리즘의 수행 시간을 평가한다.
알고리즘 문제를 풀다보면 입력의 크기에 따라 시간을 어느정도 계산할 필요가 생긴다.

입력 데이터가 최선의 경우, 평균적인 경우, 최악의 경우에 따라 시간 복잡도를 나누게 되고
문제에서는 보통 최악의 경우로 알고리즘의 성능을 파악한다.

최선의 경우는 빅 오메가 표기법, 평균은 빅 세타 표기법, 최악은 빅 오 표기법을 사용한다.

<점근적 표기>

1. O : 점근적 상한

O(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 f(n)<=c*g(n)인 양의 상수 c가 존재}

ex) {3n^2+n+3, 3n, nlogn, 5} ⊂ O(n2)

 

2. Ω : 점근적 하한

Ω(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 c*g(n)<=f(n)인 양의 상수 c가 존재}

ex) {3n^2+n+3, n^3, 3n+2} ⊂ Ω(n)

 

3. Θ

Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

= {f(n) | 충분히 큰 모든 n에 대하여 c1*g(n)<=f(n)<=c2*g(n)인 양의 상수 c1, c2가 존재}

ex) {3n^2+n+3, 2n^2+3} ⊂ Θ(n^2)

최악의 경우로 고려를 하기에 일반적으로 빅오 표기법을 사용하고 연산 횟수가 다항식이라면
최고차항에서 계수를 제외한 것으로 표현한다.

ex) 2n^2 + 3n -> O(n^2)
ex) 3n^4 -> O(n^4)
와 같은 방법이다.

코드의 각 행을 실행할 때 상수 시간이 걸린다고 가정하기 때문에

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

이렇게 n번만큼 반복문을 도는 코드는 O(n)의 시간 복잡도를 가진다고 표현할 수 있다.

시간 복잡도를 표기하는 방법은 상수, 로그, 선형, n차, 지수 시간 등이 있다.

O(1) 상수 시간

int n=0;
scanf("%d", &n);
printf("%d", n);

이 코드는 입력 값 n에 관계없이 단 한번만 실행이 되기 때문에 상수시간(O(1))의 시간 복잡도를 가진다.

O(logn) 로그 시간

입력 크기에 따라 연산 횟수가 logn에 비례해 증가한다. 이때 log 지수는 2이다.

int n=0;
scanf("%d", &n);
for(int i=1; i<=n; i*2) {
  ...
}

이런 반복문은 i가 n까지 2배씩 증가하며 도달하므로 수행 횟수가 logn에 비례한다.

O(n) 선형 시간

int n=0;
scanf("%d", &n);
for(int i=1; i<=n; i++) {
  ...
}

반복문이 n번 반복한다는 것은 연산을 n번 수행한다는 의미와 같다.
O(n)은 1차 함수와 같은 그래프기에 선형 시간이라고도 부른다.

O(n^m) m차 시간

int n=0;
scanf("%d", &n);
for(int j=1;j<=n;j++){
  for(int i=1; i<=n; i++) {
    ...
  }
}

이렇게 n번 반복하는 반복문이 2개가 중첩되어 있다면 총 실행 횟수는 n^2이다.
이것을 O(n^2)의 시간 복잡도를 갖는다고 표현하고, m번 중첩되면 시간 복잡도가 O(n^m)이 될 것이다.

O(2^n) 지수 시간

입력 크기에 따라 연산이 2^n만큼 증가하면 시간 복잡도는 O(2^n)이다.
만약 숫자로만 이루어진 n자리 비밀번호를 모든 경우의 수를 계산한다면 10^n의 연산이 필요하다.
이런 알고리즘을 지수 시간의 시간 복잡도를 가진다고 표현한다.

그래프 그림으로 보면 이렇게 이해할 수 있다.
elements에 따른 operations가 작을 수록 효율적인 알고리즘이라고 할 수 있다.

이것은 자주 사용하는 자료 구조들의 접근, 검색, 삽입, 삭제에 걸리는 연산 시간이다.
어느 정도 알아두면 유용하게 사용할 수 있다.

이것은 sort 방법에 따른 시간 복잡도이다. STL로 흔히 쓰는 sort는 O(nlogn)의 복잡도를 가진다.

그림의 출처 : https://www.bigocheatsheet.com/

공간 복잡도

시간 복잡도와 비슷하게 특정한 크기의 입력에 따라 알고리즘의 메모리 사용량을 분석하는
공간 복잡도라는 개념도 있고, 역시 빅오 표기법을 사용한다.

좋은 알고리즘이란 시간 복잡도도 작고, 공간 복잡도도 작은 알고리즘을 의미한다.
하지만 시간 복잡도와 공간 복잡도는 반비례적 관계를 가질 때가 많다.

우리가 대부분의 알고리즘을 평가하는 기준은 시간 복잡도를 기준으로 한다.

이런 시간 복잡도를 잘 이해하고 있다면 문제를 푸는데 상당히 도움이 된다.

대충 1억번 연산을 하는데 1초가 걸린다고 가정하기 때문에 입력 데이터가 10000이고 시간 제한이 1초일 때
n^2 알고리즘을 사용해도 되는구나, 입력 데이터가 백만이라면 nlogn 알고리즘을 사용해야 하는구나

이런 식으로 문제를 어느정도 파악하고 풀어나갈 수 있다.
알고리즘을 작성하면서 시간이 얼마나 걸리는지 파악하는 것은 좋은 습관인 것 같다.