시간 복잡도

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어날까

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 max_num

result = find_max_num(input)

시간 복잡도 계산방법 :
array의 길이 X array의 길이 X 비교 연산 1번
array(입력값)의 길이는 보통 N이라고 표현

$N \times 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

result = find_max_num(input)

• max_num 대입 연산 1번
• array의 길이 X (비교 연산 1번 + 대입 연산 1번)

$1+2\times N$

---

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

상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 된다.

• $2N+1$의 연산량이 나온 첫번째 풀이 방법은 $N$ 만큼의 연산량이 필요하다
• $N^2$ 의 연산량이 나온 두번째 풀이 방법은 $N^2$ 만큼의 연산량이 필요하다.