똑똑한 코드 작성을 위한 실전 알고리즘

44

똑똑한 코드 작성을 위한 실전 알고리즘

봤다. 또한 이제 경험적으로 알고리즘 구현의 런타임 성능을 평가할 수 있다. 두 경우 모두 문

제 인스턴스

N

이 두 배로 증가함에 따라 알고리즘의 증가 기준

order

of

growth

을 결정할 수 있다.

다음과 같은 주요 개념 몇 가지를 소개했다.

●

시간 복잡도 : 크기가

N

인 문제 인스턴스에서 알고리즘에 의해 실행된 주요 연산의 수를 계산해 측정.

●

공간 복잡도 : 크기가

N

인 문제 인스턴스에서 알고리즘을 실행하는 데 필요한 메모리의 양으로 측정.

다음 장에서는 알고리즘을 올바르게 분석하는 데 필요한 기술을 설명하기 위해, 점근적 분석

asymptotic

analysis

의 수학적 도구를 소개한다.

1.9

연습 문제

1.

회문 검출기(Palindrome word detector )

: 회문

palindrome

word

은 앞에서부터 읽든 뒤에서부

터 읽든 동일하게 읽히는 단어다. 예를 들면 ‘

madam

’과 같다.

N

개 문자로 구성된 단어가

회문인지 아닌지 검증하는 알고리즘을 고안해보자. [코드

1

-

8

]에 있는 두 가지 대안을 능

가하는 성능을 경험적으로 확인하자.

코드

1-8

성능 프로필이 서로 다른 네 가지 함수

def is_palindrome1(w):

"""입력으로 주어진 w와 w의 역방향 슬라이스를 생성해 같은지 비교한다.""" ...