알고리즘 시간복잡도 2

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록

 

 

 

알고리즘의 시간복잡도를 어떻게 측정하는가?

algorithm ArrayMax(A,n):     # 지금부터 ArrayMax라는 가상의 코드를 기술하겠다
	input: n개의 정수를 받는 배열 A 
    output: A의 수 중에서 최대값 리턴
	currentMax = A[0]
    for i=1 to n-1 do
    	if currentMax < A[i]:
        currentMax = A[i]
	return currentMax

A = [ ... ] , n: input size

 

1. 모든 입력에 대해 기본연산 횟수를 더한 후 평균 -> 현실적으로 불가능 (고려해야 할 입력이 무한히 많기 때문)
2. 가장 안 좋은 입력(worstcase input, 기본연산을 가장 많이 요구하는 입력)에 대한 기본연산 횟수 측정: worstcase time complexity -> 어떤 입력에 대해서도 wtc보다 수행시간이 크지 않다는 것이 보장됨.

알고리즘의 수행시간 = 최악의 입력에 대한 기본연산 횟수

대부분의 worst case는 쉽게 알 수 있음.

 

ex) 

대입연산 무조건 실행 +1

[for문 진입]

비교연산 실행 +1

if문 내의 명령문은 case by case

 

A = [2, 5, 7, 9, 15, 26]

--> if 내의 명령문이 계속해서 실행되기 때문에 기본연산 횟수가 증가함.

2n-2+1 = 2n-1번의 기본연산을 수행함. 

 

T(n) = 2n-1

 

예제

11분

혼자 해보기