시간 복잡도 판단하기

시간 복잡도란?

: 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말한다.

(입력값과 결과값이 나오는 데까지 걸리는 시간을 말한다.)

입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배를 늘어나는 지 보는 것이다.

우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?

 

시간 복잡도를 계산 할 때

입력값은 함수의 크기가 변경 될 수 있는 값을 말한다. 그렇기 때문에 다음 문제에서는 array가 입력값이다.

보통 array(입력값)의 길이는 N으로 표현하고, 각 줄이 실행되는 걸 1번의 연산이 된다라고 표현한다.

 

최댓값 찾기 알고리즘의 시간 복잡도를 판단 해보자면 

 

첫번째 방법의 시간 복잡도는

input = [3, 5, 6, 1, 2, 4]

def find_max_num(array):

    for num in array: # array의 길이만큼 아래의 연산이 실행
        for compare_num in array: # array의 길이만큼 아래의 연산이 실행
            if num < compare_num: # 비교 연산 1번 실행
                break
        else:
            return num


result = find_max_num(input)

array의 길이(N) * array의 길이(N) * 비교 연산 1번만큼의 시간이 필요하다.

그렇다면 첫번째 방법의 시간 복잡도는 다음과 같이 표현 할 수 있다.

그러면 이 함수는 N^2만큼의 시간이 걸렸구나!를 알 수 있다.

 

두번째 방법의 시간 복잡도는

def find_max_num(array):

    max_num = array[0] # 대입 연산 1번 실행       
    
    for num in array: # array의 길이만큼 아래 연산이 실행
        if num > max_num: # 비교 연산 1번 실행
            max_num = num # 대입 연산 1번 실행
    return max_num

result = find_max_num(input)

위에서 연산된 것들을 보면

1) max_num -> 대입 연산 1번

2) array 길이 * (비교 연산 + 대입 연산)

만큼의 시간이 필요하다. 첫번째 방법에서 했던 것처럼 array의 길이를 N이라고 하면

그러면 이 함수는 2N + 1만큼의 시간이 걸렸다는 걸 알 수 있다.

 

두 코드만 봐도 두번째 방법이 더 좋다는 걸 알 수 있지만 수치화 하면 얼마나 효율적인 지 정량적으로 분석 할 수 있다N의 길이가 길어 질수록, 다음과 같이 연산량이 변환한다.

이 표를 보면, 두가지를 알 수 있다.

1) N과 N^2은 N이 커질수록 더 큰 차이가 생긴다.

2) N의 지수를 먼저 비교하면 된다.

따라서 상수는 신경 쓰지 않고 입력값(함수의 크기가 변경 될 수 있는 값)에 비례해서 어느정도로 증가하는 지만 파악하면 된다.