자바로 배우는 핵심 자료구조와 알고리즘: 기술 면접에 필요한 실용주의 자료구조와 알고리즘

24

자바로 배우는 핵심 자료구조와 알고리즘

2

. 입력 데이터의 세부사항을 다루지 않으려면 가장 좋은 선택은 기대하는 입력 데이터에 대

한 평균 성능을 분석하는 것입니다. 이것이 가능하지 않을 때는 일반적인 대안으로 최악

의 시나리오를 분석하기도 합니다.

3

. 마지막으로, 한 알고리즘이 작은 문제에서는 최상의 성능을 보이지만 큰 문제에서는 다른

알고리즘이 더 좋을 수 있다는 가능성을 배제하면 안 됩니다. 이때는 보통 큰 문제에 초

점을 맞춥니다. 작은 문제에서는 알고리즘의 차이가 크지 않지만, 큰 문제에서는 그 차이

가 훨씬 거대해질 수 있기 때문입니다.

이러한 종류의 분석은 간단한 알고리즘 분류에 적합합니다. 예를 들어, 알고리즘

A

의 실행시간

이 입력

n

의 크기에 비례하고 알고리즘

B

는

n

2

에 비례하는 경향이 있다면 적어도

n

의 값이 클

때는

A

가

B

보다 빠르다고 기대합니다.

대부분 간단한 알고리즘은 다음 몇 가지 범주로 나뉩니다.

●

상수 시간

실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수 시간

constant

time

을 따른다고 합니다. 예를 들어,

n

개

의 배열에서 브래킷 연산

([ ])

을 사용하여 요소 중 하나에 접근할 때 이 연산은 배열의 크기와 관계없이 같은

수의 동작을 수행합니다.

●

선형

실행시간이 입력의 크기에 비례하면 알고리즘은 선형

linear

이라고 합니다. 예를 들어, 배열에 있는 요소를 더한

다면

n

개 요소에 접근하여

n

-

1

번 더하기 연산을 해야 합니다. 연산

(요소 접근과 더하기 )

의 총 ...