시간 복잡도 판단하기

[시간 복잡도란?]

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

(입력값이 증가할 때 걸리는 시간은 얼마나 증가하는 지 판단하는 것

 입력값이 많아졌을 때 데이터를 처리하는 데 오래걸리면 효율이 좋지 않은 코드라는 것이므로

 입력값이 많을 때 시간이 비교적 오래 걸리지 않으면 좋은 코드)

 

---

[최댓값 찾기 알고리즘의 시간 복잡도 판단해보기]

방법 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)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산하기

 

위 코드의 시간복잡도를 계산해 보면

array의 길이 * array의 길이 * 비교연산 1번

만큼의 시간이 필요함

array의 길이는 보통 "N"이라고 표현함

위의 식을 다음과 같이 표현할 수 있음

 N * N = N^2 

결론) 위의 코드는 N^2 만큼이 시간이 걸렸다고 말할 수 있음

        N^2의 시간복잡도

 

"위의 코드에서 input의 길이가 6이니까 36이라고 하면 안되나요??"

-> 시간과의 상관관계를 알고 싶을 뿐, 값을 알고 싶은 게 아님!

    그래서 수식으로 표현해야 함

 

방법2)

리스트를 하나씩 돌면서 num 과 max_num 값을 비교하는 함수

def find_max_num(array):
    max_num = array[0]         # 연산 1번 실행
    for num in array:          # 연산 1번 실행
        if num > max_num:      # 비교 연산 1번 실행
            max_num = num      # 대입 연산 1번 실행
    return max_num

result = find_max_num(input)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

위 코드의 시간복잡도를 계산해 보면

대입 연산 1번 + array의 길이 * ( 비교 연산 1번 + 대입 연산 1번 )

만큼의 시간이 필요함

array의 길이를 N이라고 하면

1 + 2N = 2N + 1

결론) 위의 코드는 2N + 1 만큼이 시간이 걸렸다고 말할 수 있음

        2N + 1 의 시간복잡도

 

N의 길이	N^2	2N + 1
1	1	3
10	100	21
100	10000	201
1000	1000000	2001

N^2의 값은 무지막지하게 커지는데 2N + 1은 N^2에 비해 한참 작다..!

제곱수일 수록 값은 커진다!

 

하지만 일일이 값을 넣어가면서 따지는건 어렵기 때문에 상수는 신경 끄고

어느정도 증가하는지에만 초점을 두기

(만약 상수의 연산량이 필요하다면 1만큼의 연산량이 필요하다고 하면 됨)

 

결론) N vs N^2