시간복잡도

swcide·2021년 6월 11일
0

시간복잡도란?

  • 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계.
    입력값이 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 만큼의 연산량이 필요하다고 말하면 된다.
profile
안녕!

관심 있을 만한 포스트

0개의 댓글