[Algorithm] 시간 복잡도(Time Complexity)

1. 시간 복잡도란?

알고리즘의 로직을 코드로 구현할 때 시간 복잡도를 고려한다는 것은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?" 이다.

 

• 효율적으로 알고리즘을 구현했다는 것은 즉, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화했다는 것이다.
• 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.

 

2. 시간 복잡도 표기법

• Big-O(빅-오) ⇒ 상한 점근
• Big-Ω(빅-오메가) ⇒ 하한 점근
• Big-θ(빅-세타) ⇒ 그 둘의 평균
• 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.

 

위 세가지중에서 보통 빅오 표기법을 통해서 알고리즘 수행 시간을 나타낸다. 최악의 경우도 고려하는 것이 바람직하기 때문이다.  

 

3. 빅오 표기법 종류

1. O(1)
2. O(n)
3. O(log n)
4. O(n2)
5. O(2n)

 

4. O(1)

 

O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

 

아래 코드의 예시가 O(1) 시간을 갖는다고 볼 수 있다. arr 배열의 길이가 커져도 인덱스를 통해서 바로 결과값을 가져올 수 있다.

public getArrayNum(int[] arr, int index) {
    return arr[index];
}

int[] arr = {1,2,3,4,5};
int index = 1;
int result = getArrayNum(arr, index);
System.out.println(result);

 

5. O(n)

O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

 

배열을 반복문을 통해서 돌면서 값을 출력해주는 코드가 있다고 했을 때 배열의 크기가 늘수록 같은 비율로 걸리는 시간이 증가한다.

 

여기서 하나 주의할 점으로는 1의 입력값이 늘때마다 수행 시간이 2초가 늘어난다면 O(2n)으로 표시할 수 있는데 O(n)으로 표시하는게 맞다.

 

왜냐하면 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기한다.

 

 

6. O(log n)

O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

 

O(log n)의 시간 복잡도를 갖는 예시로는 binary search(이분 탐색)를 들 수 있다. binary search에서는 알고리즘을 수행할 때 마다 찾아야할 대상이 절반으로 줄어든다. 이런 알고리즘이 O(log n)의 시간 복잡도를 가진 알고리즘이다.

 

6. O(n^2)

O(n2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

 

예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n2)라고 표현한다.

 

이중 for문을 돌면서 수행하는 알고리즘이 O(n^2)의 시간 복잡도를 갖는 예시로 생각할 수 있다.

 

7. O(2^n)

O(2^n)은 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

따라서 구현한 알고리즘이 O(2^n)의 시간복잡도를 갖는다면 다른 방법을 생각해보는게 좋다.

 

이에 해당하는 대표적인 알고리즘으로는 재귀적으로 수행하는 피보나치 수열이 있다.

public int fibo(int n) {

    if(n <= 1){
        return n;
    }
    
    return fibo(n-1) + fibo(n-2) 
}

 

REFERENCE

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬