알고리즘의 시간복잡도와 Big-O

들어가며

기왕이면 가장 빠른 길로 가자!
출퇴근을 하거나, 친구와의 약속 등등. 어딘가를 향할 때 우리는 항상 목적지로 가는 빠른 루트를 찾아보는 경향이 있다.
컴퓨터도 마찬가지다. 프로그램을 시행할 때 시간 복잡도가 가장 낮은 알고리즘을 선택하여 효율적으로 프로그램을 실행하려 한다.

알고리즘은 어떤 문제를 해결하기 위한 과정(명령어)들의 단계적인 나열을 말한다.
어떤 알고리즘이 더 효율적인가를 평가하는 데에는 아래와 같은 지표들이 사용된다.

 

 

알고리즘 평가 지표

• 정확성
• 작업량
• 메모리 사용량
• 최적성
• 효율성
  • 시간 복잡도 => 수행했을 때 얼만큼의 시간이 소요되는지?
  • 공간 복잡도 => 얼만큼의 메모리가 사용되는지?

보통 알고리즘에서 중요하게 여겨지는 부분은 메모리 사용량과 효율성, 그 중에서도 시간 복잡도이다.
시간 복잡도는 입력 크기 값에 대해 알고리즘의 단위 연산을 몇 번 수행했는 지에 대해 계산하여 수행 시간을 평가하는 방법이다.
시간 복잡도에 영향을 미치는 요인들은 다음과 같다.

 

시간 복잡도에 영향을 미치는 요인

• 입력 크기 (n으로 표시함)
  • 입력으로 제공되는 데이터의 크기, 개수
  • 행렬의 크기나 리스트 원소의 수 같은 것들.
  • 입력크기 n에 대한 함수를 f(n)으로 표현하고, n이 증가하면 수행 시간도 증가한다.
• 입력 데이터의 상태
  • 평균 수행 시간
  • 최선 수행 시간
  • 최악 수행 시간 ⇒ 시간 복잡도로 사용함

입력 데이터의 상태에 대해서 점근 성능 표기법으로 수행시간의 증가추세를 파악할 수 있는데,
중요하지 않은 상수와 계수들을 제외하고 아래와 같이 최고차항만을 계산한다.
최고차항이 가장 큰 영향을 미치기 때문이다.

1            O(1)
3n+5        O(n)
2n^2+5n+1    O(n^2)

 

 

점근적 표현법에는 세가지 경우가 있지만 보통은 최악의 경우를 따지는 빅오 표기법을 사용한다.
최악의 경우일 때를 판단하면 평균과 흡사한 성능으로 예측하기 좋기 때문이다.

3가지 점근적 표현법

• O 빅오 : 최악의 상황을 고려하여 성능 측정 결과 표현 (대부분의 알고리즘 표현)
• 𝜽 세타 : 평균적인 경우에서의 성능 측정 결과 표현
• Ω 오메가 : 최선의 상황일 때의 성능 측정 결과 표현

 

 

 

주요 O-표기 간의 연산 시간의 크기 관계

https://www.bigocheatsheet.com/

O(1) < O(log n) < O(n) < O(n log n) <<<<<  O(n^2) < O(n^3) < O(2^n)

빅오의 복잡도를 나타낸 차트를 식으로 나열해보면 이렇게 표현해볼 수 있다.
왼쪽으로 갈수록 시간이 적게 소요되며 오른쪽으로 갈수록 시간이 더 많이 소요된다.
제일 왼쪽의 상수시간 O(1)이 가장 효율적이며 제일 오른쪽의 지수 시간 O(2^n)이 가장 비효율적이다.

 

 

 

 

빅오 표기법 예제

자바스크립트로 보는 대표적인 빅오 표기법 예시 코드들.

 

• O(1)

return 값은 상수이기 때문에 시간복잡도는 O(1)이다.

function big_o(n) {
  let sum = 0;
  sum = n * 2;
  return sum; // 2이 나오기 때문에 O(1)
}

 

 

 

• O(n)

for문이 대표적이다. for문은 중첩될수록 n 제곱의 시간복잡도를 가진다.

// for문이 많을수록 n 제곱이 된다.
function big_o(arr, n) {
  let sum = 0;
  for (let i = 0; i < n; i++) {
    sum += arr[i];
  }
  return sum; // n+2가 나오기 때문에 O(N)
}

 

 

 

• O(n^2)

이중 for문이 대표적인 예시다. for문에 비해 현저히 느린 시간 복잡도..

function big_o(arr, n) {
  let sum = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      sum += arr[i][j];
    }
  }
  return sum; // n^2 + 2 => O(n^2)
}

 

 

 

• O(logN)
  이진 탐색이나 병합정렬, 분할정복 등에서 많이 나오는 시간 복잡도이다.

function big_o(n) {
  let sum = 0;
  for (let i = 0; i < n; i *= 2) {
    sum += 2;
  }
  return sum; // n/2 + 2 => O(logN). O(n)보다 더 빠르다.
}

 

 

 

 

아래는 참고할 수 있는 각 자료구조와 정렬 알고리즘의 시간복잡도, 공간복잡도를 비교한 표이다.

https://www.bigocheatsheet.com/

https://www.bigocheatsheet.com/