시간 복잡도

시간 복잡도란?

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

첫 번째 방법

---

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의 길이 X array의 길이 X 비교 연산 1번

array(입력값)의 길이는 보통 N이라고 표현한다.

• N X N

  이 함수는 $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

• 위 연산들을 다 더해봤을 때
  • max_num 대입 연산 1번
  • array의 길이 X (비교 연산 1번 + 대입 연산 1번)

• 1 + 2 X N

  이 함수는 $2N+1$ 만큼의 시간이 걸렸겠구나! 라고 말할 수 있다.

• 두 번째 방식이 더 시간이 적게 걸리는 효율적인 코드
• 상수는 시간 복잡도에 영향을 주기엔 미비하므로 신경쓰지말자