TimeComplexity.md

시간복잡도와 Big-O 표기법 (Time Complexity & Big-O)

written by sohyeon, hyemin 💡

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

1-1. 알고리즘의 분석

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

수행시간

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

알고리즘 수행시간

주어진 문제의 입력크기가 다양하기 때문에
최악, 최상, 평균적인 경우 총 3개의 case를 가질 수 있는데
우리는 최악의 경우에 주로 관심을 둘 것이다.

최악의 경우는 모든 입력에 대한 수행시간의 상한이 되며,
이보다 더 나쁜 경우는 존재하지 않고 최악의 경우가 빈번하기도 함  

1-2. 시간복잡도

가장 널리 사용되는 알고리즘의 수행시간 기준
알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현

<시간 복잡도와 입력 크기의 관계>

시간 복잡도가 높다는 것은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 증가한다는 의미이다.  
하지만 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다.  
입력의 크기가 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다.

시간 복잡도를 표기하기 쉽게하기 위해 증가차수, 점근적 효율성을 기준으로 알고리즘의 수행시간을 나타낼 것이다.

증가차수

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

점근적 효율성

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

점근적 표기 방식에 따라,

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

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

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

세가지 방식으로 시간복잡도를 나타내는데 사용한다.
이 중에서도 최악의 경우인 빅오를 사용해 최악의 경우를 판단하면 평균과 가까운 성능으로 예측하기 쉽다.

2. 빅오 표기법(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)이다.

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

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)

2) 성능비교

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