시간 복잡도와 Big O(빅-오) 표기법

어느덧 시간 복잡도 단계에 접어 들었다.

사실 시간 복잡도 쪽은 정확한 개념을 잡지 못한 상태여서 우선 개념을 먼저 잡는 것이 필요했다.

간단하게 찾아 보았던 정보들을 정리해 보고자 한다.

 

시간 복잡도 - 효율에 관하여...

백준에서 문제를 풀다보면 코드의 정확도는 당연히 갖춰줘야 하지만 가독성이나 효율성에 대해서 여러번 생각해 볼때가 있다.

특히, 속도라는 것은 바로 눈으로 확인 가능한 부분이기도 하고 속도가 나오지 않으면 코드자체가 돌지 않는 경우도 발생하기에 어떤 방법이 가장 빠른지 판단이 필요할 때가 있는데, 이때 알고리즘의 실행속도를 수치적으로 계산한 것을 시간복잡도라고 한다.

 

시간 복잡도의 핵심 요소는 반복문인데, 입력이 들어왔을 때 반복을 얼마나 하는지가 보통 알고리즘의 수행 시간을 증가시키기 때문이다.

시간복잡도의 표기법에는 3가지 종류가 있다.

• Big O(빅-오) 표기법 [ O(N) ]
  - 알고리즘 최악의 실행 시간을 표기(최악의 상황에서도 보장하는 알고리즘의 수행 속도를 의미
  - 성능 보장을 의미하기때문에 가장 많이 사용하는 표기법
• 오메가 표기법 [Ω(N)]
  - 알고리즘 최상의 실행 시간을 표기
• 세타 표기법 [Θ(N)]
  - 알고리즘 평균 실행 시간을 표기

 

이중에서 빅-오 표기법을 가장 많이 사용하는데, 위에 설명되어 있듯 성능의 보장을 의미하기 때문이다. (아무리 느려도 이정도 속도는 나온다는 것을 의미한다.)

빅오 표기법을 잘 정리해둔 글이 있어 공유해본다.

 

https://devraphy.tistory.com/40

Data Structure - 시간 복잡도(Time Complexity)

 

1) O(1) - constant time

입력 값의 크기에 상관없이 항상 같은 시간이 걸리는 알고리즘이다.

public static int getFirst(int[] nums) {
    return nums[0];
}

예를 들어, 특정 인덱스의 값만을 찾는 코드가 있다면, 입력값이 100이든 1000이든 10000이든 상관없이 항상 같은 시간이 걸릴 것이다.

 

2) O(n) - linear time

입력값의 크기에 비례해서 처리시간이 증가하는 알고리즘이다.

public static int[] reverse(int[] nums) {
    int[] reversed = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        reversed[nums.length - i - 1] = nums[i];
    }
    return reversed;
}

예를 들어, 특정 배열을 입력받아 뒤집는 알고리즘이 있는데 1이 입력되었을때, 1초가 걸렸다고 하면 5가 입력되면 5초가 걸릴것이다. 이렇게 선형으로 시간이 늘어나는 알고리즘을 말한다.

 

3) O(n의 2승) - quadratic time

동일한 반복회수를 갖는 이중 for문 같은 알고리즘이다.

for문 하나당 O(n)의 시간 복잡도를 갖게 되는데, 이중 for문의 경우 O(n) * O(n)만큼의 시간복잡도를 갖게 되므로 O(n^2)가 된다.

public static void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[minIdx]) {
                minIdx = j;
            }
        }
        int tmp = nums[i];
        nums[i] = nums[minIdx];
        nums[minIdx] = tmp;
    }
}

4) O(logn) 

이진 탐색이 O(log n)의 대표적인 예시이다.

연산 / 처리과정을 거칠 때마다 절차가 반씩 줄어드는 것을 의미한다.

public static void mergeSort(int[] nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

빅 오 표기법에서 중요한 것이 있는데...

빅 오 표기법에서는 상수를 과감하게 버린다.

예를 들어 for 문을 2번 돌린다고 가정 할 때, (2중 for문이 아니라 단일 for문을 2번 돌린다고 생각해 보자)

알고리즘의 시간복잡도는 O(2n)이 될 것이다.

 

그러나 빅 오 표기법에서는 상수 2를 버리고 O(n)만큼의 시간복잡도가 걸린다고 표기한다.

이렇게 표기하는 이유는 빅 오 표기법이 입력값에 따른 처리시간의 증가율을 예측하기 위한 방법이기 때문이다.

즉, 빅 오 표기법은 실제 알고리즘의 처리시간을 따지는 방법이 아니다.

상수는 고정된 숫자이기 때문에, 증가율에 따라 고정된 값 만큼의 영향을 미치기 때문에 무시하는 것.

무한한 입력값이 들어온다고 가정했을때에 알고리즘의 증가율에서 중요한 것은 상수가 아니라 최고차항의 차수이기 때문에 상수는 중요하게 취급 되지 않는다고 생각하면 될 것이다.