[algorithm] 시간 복잡도와 빅오 표기법(big-O notation)

알고리즘을 공부하다 보면 필수적으로 듣는 용어가 시간복잡도와 빅오 표기법이다.

---

빅오 표기법이란?

먼저 쉽게 말하면 알고리즘 최악의 실행 시간을 표기해 아무리 최악의 상황에도 이 정도 실행 시간은 보장한다는 뜻이다.

컴퓨터과학(Computer Science)에서 알고리즘이란 특정 문제를 해결하기 위한 방법으로 알고리즘의 시간 복잡도를 나타내는 수학적 표기법 중 하나이다.

이는 주어진 알고리즘이 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 나타낸다. 일반적으로 알고리즘의 최악의 경우를 고려하여 시간 복잡도를 나타내고, 이를 O(..) 형태로 표기하며, 괄호 안에 알고리즘의 실행 시간이 입력 크기에 대해 어떻게 증가하는지를 나타내는 함수를 뜻한다.

 

본래 알고리즘의 효율성을 측정하는 가장 간단한 방법은 “직접 재는 것”이다. clock()함수나 time() 함수를 통해 프로그램의 수행시간을 직접 잴 수 있다.

하지만 이러한 방법의 문제점은 알고리즘이 간단한 경우에는 쉽게 구현하고 사용할 수 있지만 복잡한 경우에는 구현하는데에 있어 어려움이 존재하고 이는 실험되지 않은 입력에 대해서는 수행시간을 주장할 수 없다는 것이다.

수행시간을 비교하려면 반드시 똑같은 하드웨어를 사용해서 알고리즘의 수행시간을 측정해야 한다. 그 뿐 아니라 소프트웨어 환경 등등의 부가적인 요소가 많기 때문에 구현하지 않고도 알고리즘의 효율성을 따질 수 있는 방법이 개발되었다.

 

표기법은 3가지 형태가 있다.

• 최상의 경우: 오메가 표기법
• 평균의 경우: 세타 표기법
• 최악의 경우: 빅오 표기법

일반적으로 평균의 경우인 세타 표기법을 사용하면 좋겠지만 구하기가 까다로운 이유로 최악의 경우인 빅오 표기법을 사용한다.

수학적 정의

수학적 정의는 이렇게 나타낼 수 있다.

---

시간 복잡도와 공간 복잡도

빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다. 복잡도란 알고리즘의 성능을 나타내는 기준을 의미한다.

시간 복잡도(time complexity) : 알고리즘이 입력 데이터의 크기가 n일 때 실행되는 시간(얼마나 빠르게 처리하는지)

공간 복잡도(space complexity): 알고리즘이 사용해야 하는 메모리 공간의 크기(메모리를 얼마나 사용하는지)

 

---

빅오 표기법의 특징

빅오 표기법은 알고리즘의 성능을 간결하게 표현하고 비교하기 위한 몇 가지 특징이 존재한다.

 

먼저 빅오 표기법은 상수항을 무시한다.

빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향받기 때문에 상수항 같은 사소한 부분은 무시한다.

 

또한 빅오 표기법은 영향력이 없는 항은 무시한다.

빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.

 

이를 통해 알고리즘의 실행 시간이나 메모리 사용량을 간단하게 파악하고 비교할 수 있도록 도와준다.

 

---

빅오 표기법의 종류

1. 상수형 빅오 O(1)

먼저 상수형은 알고리즘의 실행 시간이 입력 크기와 무관할때 이다. 데이터 수에 상관없이 연산 횟수가 고정이다.

ex) stack - push/pop, 배열의 첫 번째 요소에 접근하는 경우

 

예시

int main(){
    int a,b;
    scanf("%d %d", &a,&b);
    int result = a+b;
    printf("%d",result);
}

 

a b를 선언할 때, 입력 받을 때, 계산 대입 출력 모두 상수시간으로 계산됨으로 O(1)이다.

 

2. 로그형 빅오 O(log n)

로그형 빅오는 입력 크기의 로그에 비례해 실행 시간이 증가할 때이다. 데이터 수의 증가율에 비해 연산 횟수의 증가율이 낮기 때문에 매우 큰 입력에 대해서도 효율적으로 동작하며 빠른 실행 속도를 보장한다.

ex) BinarySearch

 

3. 선형 빅오 O(n)

입력 크기에 비례해 실행 시간이 증가할 때이다. 배열의 모든 요소를 한 번씩 순회하는 것과 같이 입력 크기에 선형적으로 비례하여 작업을 수행하기에 요소의 개수에 비례해 실행 시간이 증가한다.

ex) for문

 

예제

int main(){
  int n;
  scnaf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    // 필요한 코드 수행
  }
}

for문 위 두줄은 상수이고 for문을 n번 실행하므로 O(N)이다.

 

4. 선형 로그 빅오 O(N log n)

입력 크기에 대한 로그와 입력 크기에 비례해 실행 시간이 증가하는 경우이다. 선형 시간과 로그 시간의 곱으로 표현한다.

ex) Quick Sort, Merge Sort

 

예제

 

5. 이차형 빅오 O(n^2)

입력 크기의 제곱에 비례해 실행 시간이 증가한다. 제곱에 비례해 증가하기 때문에 입력 크기가 커질수록 실행 시간이 기하급수적으로 증가하게 된다.

ex) 이중for문, bubble sort, selection sort

 

예제

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

 

이중 for문은  O(n^2)이라고 생각하면 되지만. 수학적 계산법을 보면 다음과 같다.

---

 

시간복잡도 순서

 

왼쪽인 O(1)로 갈수록 실행 횟수가 적은 것, 즉 시간 복잡도가 낮은 것이고 

오른쪽인 O(2^n)로 갈수록 실행 횟수가 많은것, 즉 시간 복잡도가 높은 것이다.

 

시간 복잡도를 구하는 요령

문제의 시간 복잡도 유형을 빨리 파악할 수 있도록 아래의 예를 통해 분석해 볼 수도 있다.

• 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
• 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
• 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복할 경우 : O (n + m) -> O (n)
• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
• 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복할 경우 : O (n * m) -> O (n²)
• 컬렉션 정렬을 사용하는 경우 : O(n*log(n))

정렬 알고리즘 비교

정렬 알고리즘	공간 복잡도	시간 복잡도
	최악	최선	평균	최악
Bubble Sort	O(1)	O(n)	O(n2)	O(n2)
Heapsort	O(1)	O(n log n)	O(n log n)	O(n log n)
Insertion Sort	O(1)	O(n)	O(n2)	O(n2)
Mergesort	O(n)	O(n log n)	O(n log n)	O(n log n)
Quicksort	O(log n)	O(n log n)	O(n log n)	O(n2)
Selection Sort	O(1)	O(n2)	O(n2)	O(n2)

---

빅오 표기법의 한계

빅오 표기법은 알고리즘의 시간 복잡도를 간단하고 명확하게 표현하는 강력한 도구이지만 몇 가지 한계점이 존재하게 된다.

 

1. 최악vs평균

빅오 표기법은 주로 알고리즘의 최악의 경우 시간 복잡도를 나타낸다.

하지만 실제로 알고리즘이 평균적으로 어떻게 동작하는지 고려하지 않는다.

따라서 평균적인 경우에는 빅오 표기법으로 나타낸 시간 복잡도보다 더 나 은 성능을 보일 수 있다.

 

2. 입력 크기와 알고리즘 복잡성

입력 데이터의 구성, 문제의 본질, 알고리즘의 구현 방식 등 다양한 요인은 빅오 표기법으로 충분히 설명되지 않을 수 있다. 따라서 빅오 표기법만으로 알고리즘을 평가하는 것은 어려움이 존재할 수 있다.

 

3. 실제 환경과 하드웨어

빅오 표기법은 알고리즘의 이론적인 분석을 위한 도구이기 때문에 실제

환경에서의 성능과는 다를 수 있다. 하드웨어의 성능, 메모리 사용 방식 등 은 빅오 표기법으로는 고려되지 않는 요소들이기 때문이다.