시간복잡도

시간복잡도란?

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

계산법?

• 각 줄이 실행되는 것을 1번의 연산으로 생각후 계산

• array(N)의 길이 X array(N)의 길이 X 비교 연산 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의 길이 X array의 길이 +비교연산 1
2. $1N\times N = N^2$

따라서 시간복잡도는 $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

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. max_num 대입 연산 1번
2. array의 길이 X (비교 연산 1번 + 대입 연산 1번)
3. $1+2\times N = 2N+1$

계산식에서 수가 커질수록 $N^n$의 값이 무조건 크기때문에 상수는 무시해도 된다.
그러므로 위의 값은 $N$이다.

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