[TIL] 16 시간복잡도

시간복잡도란 무엇인가

위키백과에서는 시간복잡도란

'입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다' 라고 정의한다.

다시말해, 입력값이 변할 때 연산횟수에 비해 해당 연산이 얼마나 오래걸리냐를 뜻한다.

보통 시간복잡도를 표현하기 위해서 빅오표기법을 이용한다.

http://bigocheatsheet.com/

 

시간복잡도가 낮은 알고리즘( == 효율적인 알고리즘) 을 목표로 해야한다.

빅오표기법으로 시간복잡도를 표현하는 형태는 아래와 같다.

 

1. 상수 형태

O(1)로 표현한다.

이는 입력값이 얼마나 되든 연산 시간이 늘어나지 않으며, 입력한 값에 상관없이 바로 출력가능하다.

public class Main {
    public static void main(String[] args){
        System.out.println("1");
    }
}

 

이 예시로는 백준 문제가 있다.

24262

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

위와 같은 알고리즘이 있을 때 

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

 

>> 입력값이 어떻게 되든 A[i]를 return 하는 수행은 한번만 이루어진다. 그러므로 첫째줄은 1, 둘째줄은 0이 출력되어야한다.

 

2. 로그형태

O(log n)로 표현한다.

이때 log의 밑은 2다.

이는 이진탐색이 대표적인 예이다.

* 이진탐색 

: Binary Search라 하며 정렬되어있는 배열에서 중간값을 꺼내어 내가 찾고자 하는 값과 크기를 비교하며 데이터를 찾는 방법이다. 꼭!! 정렬이 되어있어야한다.

 

ex) 

오름차순 배열 arr이 있다.

{1,4,6,18,40,44,60} 

여기에서 이진탐색을 사용하여 6이라는 값을 찾기 위해서는 아래 방법과 같다.

1. 배열의 중간값인 18을 선택한다.

2. 18과 6을 비교한다. 이때 내가 찾고자 하는 6은 18보다 작으므로 6은 중간보다 왼쪽에 있음을 알 수 있다.

3. 중간값 18을 기준으로 왼쪽 배열을 가져온다. {1,4,6}

4. 가운데 값 4를 선택한다.

5. 4와 6을 비교한다. 이때 내가 찾고자 하는 6은 4보다 크므로 6은 중간보다 오른쪽에 있음을 알 수 있다.

6. 중간값 4를 기준으로 오른쪽 배열을 가져온다. {6}

배열에 값이 하나 남았다. 값을 확인해보면 내가 찾던 6이다.!

 

위 예제에서 내가 다루어야하는 원소의 개수는

7 -> 3 -> 1 이 되며, 이때 실행횟수는 3이된다.

내가 다루어야하는 원소의 개수를 N으로 두고, 이를 식으로 세우면

N, N/2, N/4 , N/8 ........1 이 되는데, ( 위 예제에서는 분모가 4일때 이미 1이 되지만, N이 더 컸을때도 가정한다.)

이때 실행횟수를 K로 두고 이를 식으로 세우면

2^K = N

log2^N = K 가 되어 빅오 표기법으로 O(log N)으로 표현하게 된다.