시간복잡도

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말합니다!
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것.
우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.

시간 복잡도 판단하기

첫번째 방법

	예문
    def find_max_num(array):
    for num in array:
        for compare_num in array:
            if num < compare_num:
                break
        else:
            return num

각 숫자마다 모든 다른 숫자와 비교해서 최대값인지 확인합니다. 만약 다른 모든 값보다 크다면 반복문을 중단한다. 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산

array의 길이 X array의 길이 X 비교 연산 1번
이제 이 함수는 $N^2$ 만큼의 시간이 걸렸겠구나! 라고 말할 수 있다.

두번째 방법

def find_max_num(array):
  max_num = array[0]        
  for num in array:      
      if num > max_num:  
          max_num = num
  return max_num

리스트를 하나씩 돌면서 num 과 max_num 값을 비교하는 함수이다.
1. max_num 대입 연산 1번
2. array의 길이 X (비교 연산 1번 + 대입 연산 1번)

만큼의 시간이 필요하다. 첫 번째 방법에서 했던 것처럼 array 의 길이를 N이라고 하면, 다음과 같이 표현할 수 있다.
이제 이 함수는 $2N+1$ 만큼의 시간이 걸렸겠구나! 라고 말할 수 있다.

정량적 비교분석

이를 수학적으로 표현해보면 첫 번째 방법은 $N^2$, 두 번째 방법은 $2N+1$ 이라는 식이 나온다는 걸 알 수 있다. 그러면 N 의 길이가 길어질수록, 다음과 같이 연산량이 변화한다.

1. $N$ 과 $N^2$ 은 N 이 커질수록 더 큰 차이가 나는구나!
2. $N$의 지수를 먼저 비교하면 되겠구나.

매번 코드를 매 실행 단위로 이렇게 몇 번의 연산이 발생하는지 확인하는 건 불가능하다.
따라서 상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 된다.

✔tip

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

참고로, 만약 상수의 연산량이 필요하다면, $1$ 만큼의 연산량이 필요하다고 말하면 된다.