[알고리즘] 시간복잡도와 Big-O 표기법

알고리즘 강의를 수강할때 작성한 강의 노트를 기반으로 포스팅합니다.

---

1. 알고리즘의 분석과 수행시간

• 알고리즘의 분석: 알고리즘을 실행하는데 필요한 자원을 예측하는 것
  메모리, 통신대역, 하드웨어와 같은 자원이 측정의 관심대상이 되기도 하지만 대부분의 경우
  측정대상은 계산시간이다.

• 수행시간: 기본연산개수 또는 실행된 단계의 횟수
  (즉, 알고리즘의 수행시간은 각 명령문 수행시간의 합이다.)

알고리즘 수행시간

주어진 문제의 입력크기가 다양하기 때문에

최악, 최상, 평균적인 경우 총 3개의 case를 가질 수 있는데

우리는 최악의 경우에 주로 관심을 둘 것이다.

(모든 입력에 대한 수행시간의 상한이 되며 이보다 더 나쁜 경우는 존재하지 않기 때문에,

그리고 최악의 경우가 빈번하기도 함)

 

2. 시간복잡도

증가차수, 점근적 효율성을 기준으로 알고리즘의 수행시간을 나타낼 것이다.

• 증가차수: 더 단순하게 추상화하여 수행시간에 대한 증가비율 또는 증가차수를 이용하는 것
  차수가 가장 높은 항만 고려하고 상수 계수는 무시한다.

• 점근적 효율성: 입력크기가 극한으로 증가할 때
  어떤 알고리즘의 수행시간이 어떻게 증가하는지에 관심을 두고 점근적으로
  더 효율적인 알고리즘이 가장 좋은 선택이 되는 것

점근적 표기 방식에 따라,

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)

• 평균의 경우 : 세타 표기법 (Big-θ Notation)

• 최악의 경우 : 빅오 표기법 (Big-O Notation)

세가지 방식으로 시간복잡도를 나타내는데 사용한다.

이 중에서도 최악의 경우인 빅오를 사용해 최악의 경우를 판단하면 평균과 가까운 성능으로 예측하기 쉽다.

 

3. 빅오 표기법(Big-O Notation)

빅오 표기법은 점근적 상한을 나타내는 것이다.

입력의 크기가 극한으로 증가할때 최고 차항의 차수가 가장 영향을 많이 끼치기 때문에

가장 높은 항을 제외하고 다른 항은 다 제거하는 표기법이다.

 

즉, 시간복잡도에 가장 큰 영향을 미치는 차항으로 시간복잡도를 나타내는 표기법이다.

 

T(n)=n^2+2n+9 	    # O(n2)

T(n)=n^4+n^3+n^2+1  # O(n4)

T(n)=5n^3+3n^2+2n+1 # O(n3)

최고 차항을 제외하고 다 제거하고 계산하기 때문에 계산이 매우 간단하다.

알고리즘의 시간복잡도는 반복문에 의해 결정되므로 반복문이 몇번 실행되는지 보면 된다.

 

예시)

for(int i=0; i<N; i++){
	...
    for(int k=0; k<N; k++){
    	...
    }
}

위와 같은 경우 N번 수행되는 반복문이 두번 중첩되어있기 때문에 시간복잡도는 O(N^2)이다.

 

4. Big-O 표기법의 종류와 성능

4-1. Big-O 표기법의 종류

빅오 표기법의 종류

• O(1) - (상수) Constant

  • 입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다.

  • 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.

• O(logN) Logarithmic

  • 데이터양이 많아져도, 시간이 조금씩 늘어난다.

  • 시간에 비례하여, 탐색 가능한 데이터양이 2의 n승이 된다.

  • 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

  • 만약 입력 자료의 수에 따라 실행 시간이 이 log N 의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 이 유형은 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형이다.

  • Binary Search

• O(N) Linear

  • 데이터양에 따라 시간이 정비례한다.

  • linear search, for 문을 통한 탐색을 생각하면 되겠다.

• O(N log N) log linear

  • 데이터양이 N배 많이 진다면, 실행 시간은 N배 보다 조금더 많아 진다. (정비례 하지 않는다.)

  • 이 유형은 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고,나중에 다시 그것들을 하나로 모으는 경우에 나타난다. N이 두배로 늘어나면 실행 시간은 2배보다 약간 더 많이 늘어난다.

  • 퀵소트, 머지소트

• O(N^2) Quadratic

  • 데이터양에 따라 걸리는 시간은 제곱에 비례한다. (효율이 좋지 않음, 사용하면 안된다)

  • 이 유형은 이중루프내에서 입력 자료를 처리 하는 경우에 나타난다. N값이 큰값이 되면 실행 시간은 감당하지 못할 정도로 커지게 된다.

  • 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱

  • 2중 for 문을 사용하는 버블소트, 삽입정렬(insertion sort)

4-2. 성능비교

• 성능 순서 : O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)

성능 비교

 

참고: 알고리즘 시간 복잡도 분석

       자료구조, 알고리즘 - 성능측정 (Big-O)

---

기본적인 자료구조에 대한 포스팅을

자바를 기반으로 이어서 해보겠습니다.